QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164838 | #4218. Hidden Graph | training4usaco | WA | 1ms | 3632kb | C++17 | 1.4kb | 2023-09-05 14:00:35 | 2023-09-05 14:00:35 |
Judging History
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;
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) {
for(int j = 1; j <= n; ++j) {
color[i] = used[i] = 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3632kb
input:
3 1 2
output:
? 2 1 2 ! 1 1 2
result:
wrong answer read 1 edges but expected 3 edges