QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164861#4218. Hidden Graphtraining4usacoWA 3ms3776kbC++171.5kb2023-09-05 14:13:542023-09-05 14:13:55

Judging History

你现在查看的是最新测评结果

  • [2023-09-05 14:13:55]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3776kb
  • [2023-09-05 14:13:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define ff first
#define ss second

const int MAXN = 2e3 + 5;

int n;
vector<int> adj[MAXN];
int color[MAXN], used[MAXN];
set<int> sets[MAXN];

pii ask(set<int> nodes) {
	cout << "? " << nodes.size() << " ";

    for(auto node : nodes) cout << node << " ";
    cout << endl;

	// cout << "hello: " << endl;

    int a, b; cin >> a >> b;
    return {min(a, b), max(a, b)};
}

void magic(int u) {
	for(auto v : adj[u]) {
		if(color[v] != 0) used[color[v]] = u;
	}

	for(int c = 1; c <= n; ++c) {
		if(used[c] != u) {
			color[u] = c; sets[u].insert(c);
			break;
		}
	}

	for(auto v : adj[u]) {
		if(color[v] == 0) magic(v);
	}
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n;

	vector<pii> ans;

	for(int i = 2; i <= n; ++i) {
	   // cout << "i: " << i << endl;
		for(int j = 1; j <= n; ++j) {
			color[j] = used[j] = 0;
			sets[j].clear();
		}

		for(int j = 1; j < i; ++j) {
			if(color[j] == 0) magic(j);
		}

		for(int c = 1; c <= n; ++c) {
			if(sets[c].empty()) break;

			sets[c].insert(i);

			pii edge = ask(sets[c]);

			while(edge.ff != -1) {
				ans.push_back(edge);
				adj[edge.ff].push_back(edge.ss); adj[edge.ss].push_back(edge.ff);
				sets[c].erase(edge.ff);

				if(sets[c].size() < 2) break;

				edge = ask(sets[c]);
			}
		}
	}

	cout << "! " << ans.size() << endl;
	for(auto edge : ans) cout << edge.ff  << " " << edge.ss << endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

3
1 2
1 3
2 3

output:

? 2 1 2 
? 2 1 3 
? 2 2 3 
! 3
1 2
1 3
2 3

result:

ok correct

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 3776kb

input:

10
1 2
1 3
-1 -1
1 4
-1 -1
-1 -1
-1 -1
2 5
2 5
2 5
-1 -1
2 6
2 6
2 6
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1

output:

? 2 1 2 
? 2 1 3 
? 2 2 3 
? 2 1 4 
? 2 2 4 
? 2 2 4 
? 2 1 5 
? 2 2 5 
? 2 2 5 
? 2 2 5 
? 2 1 6 
? 2 2 6 
? 2 2 6 
? 2 2 6 
? 2 1 6 
? 2 1 7 
? 2 2 7 
? 2 2 7 
? 2 2 7 
? 2 1 7 
? 2 1 7 
? 2 1 8 
? 2 2 8 
? 2 2 8 
? 2 2 8 
? 2 1 8 
? 2 1 8 
? 2 1 8 
? 2 1 9 
? 2 2 9 
? 2 2 9 
? 2 2 9 
? 2 1 9 
? 2...

result:

wrong answer read 9 edges but expected 12 edges