Codeforces #796 : Div1 B. Railway System

Bまで簡単でCから難しかった回。
https://codeforces.com/contest/1687/problem/B

問題

N点M辺の無向グラフがある。
各辺には長さが設定されているが、その値は不明である。

以下のクエリを2M回行い、最小全域木の総長を求めよ。

• 辺の部分集合を指定し、最大全域木の総長を返す

解法

まず1辺のみのクエリを行い各辺の長さを確定する。
あとは短い順に辺を追加してクエリを実行しよう。クエリの結果が、追加辺分増加するなら、それは最小全域木に使われる辺である。

int N,M;
int V[505];
int A[505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<pair<int,int>> C;
	FOR(i,M) {
		cout<<"? ";
		FOR(j,M) cout<<(i==j);
		cout<<endl;
		cin>>V[i];
		C.push_back({V[i],i});
	}
	sort(ALL(C));
	int pre=0;
	FORR2(a,b,C) {
		A[b]=1;
		cout<<"? ";
		FOR(j,M) cout<<A[j];
		cout<<endl;
		cin>>x;
		
		if(pre+a==x) {
			pre+=a;
		}
		else {
			A[b]=0;
		}
	}
	cout<<"! "<<pre<<endl;
	
}

まとめ

簡単だと思ったら750ptか。