QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110986 | #4218. Hidden Graph | Retrieve_72 | TL | 0ms | 0kb | C++14 | 2.2kb | 2023-06-05 10:17:51 | 2023-06-05 10:17:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << var << "; "
#define int long long
int n, m, tot, ind[2010], lnd[2010], col[2010];
set<int> sub[2010], tmp; vector<int> g[2010];
void getsub(int n) {
set<pii> st; st.clear();
for (int i = 1; i <= n; i++)
st.insert(mp(ind[i], i));
memcpy(lnd, ind, sizeof lnd);
memset(col, 0, sizeof col); tot = 0;
while (st.size()) {
set<pii>::iterator it = st.begin(); st.erase(it);
int u = (*it).se;
vector<int> c; c.clear();
for (int j = 0; j < g[u].size(); j++) {
if (col[g[u][j]]) c.pb(col[g[u][j]]);
st.erase(mp(ind[g[u][j]], g[u][j])); ind[g[u][j]]--; st.insert(mp(ind[g[u][j]], g[u][j]));
}
sort(c.begin(), c.end());
int lst = 0, now = 0;
for (int i = 0; i < c.size(); i++)
if (c[i] > lst + 1) {
now = lst + 1; break;
} else lst = c[i];
col[u] = now;
if (!now) col[u] = now = ++tot;
}
}
signed main() {
srand(time(0));
cin >> n;
tot = 1; sub[1].insert(1);
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= tot; j++) {
cout << "? " << sub[j].size() + 1 << " " << i << " ";
tmp = sub[j];
for (set<int>::iterator it = tmp.begin(); it != tmp.end(); it++) cout << *it << " "; cout << endl;
int u, v;
cin >> u >> v;
if (u != i) swap(u, v);
if (u == -1 && v == -1) {
}
else {
g[u].pb(v), g[v].pb(u); m++; ind[u]++, ind[v]++;
while (true) {
tmp.erase(v);
if (tmp.empty()) break;
cout << "? " << tmp.size() + 1 << " " << i << " ";
for (set<int>::iterator it = tmp.begin(); it != tmp.end(); it++) cout << *it << " "; cout << endl;
cin >> u >> v;
if (u != i) swap(u, v);
if (v != -1) {
g[u].pb(v), g[v].pb(u); m++; ind[u]++, ind[v]++;
} else break;
}
}
}
for (int i = 1; i <= tot; i++) sub[i].clear();
getsub(i);
for (int j = 1; j <= i; j++) sub[col[j]].insert(j);
}
cout << "! " << m << endl;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < g[i].size(); j++)
if (g[i][j] > i) cout << i << " " << g[i][j] << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 1 2
output:
? 2 2 1