Submission #52291

#TimeUsernameProblemLanguageResultExecution timeMemory
52291tmwilliamlin168ICC (CEOI16_icc)C++14
100 / 100
188 ms988 KiB
#include <icc.h> #include <bits/stdc++.h> using namespace std; const int mxN=100; int cci; bool vis[mxN]; vector<int> adj[mxN], ccs[mxN], qa[2]; void dfs(int u) { vis[u]=1; ccs[cci].push_back(u); for(int v : adj[u]) if(!vis[v]) dfs(v); } /* int query(int as, int bs, int *aa, int *ba) { cout << "Query " << as << " " << bs << endl; for(int i=0; i<as; ++i) cout << aa[i] << " "; cout << endl; for(int i=0; i<bs; ++i) cout << ba[i] << " "; cout << endl; int r; cin >> r; return r; } void setRoad(int u, int v) { cout << "Set road " << u << " " << v << endl; } //*/ void run(int n) { for(int it=0; it<n-1; ++it) { for(int i=0; i<n; ++i) { // cout << "hi1 " << i << endl; if(!vis[i]) { // cout << "hi2 " << i << endl; dfs(i); ++cci; } } for(int i=0; ; ++i) { qa[0].clear(); qa[1].clear(); for(int j=0; j<cci; ++j) for(int u : ccs[j]) qa[j>>i&1].push_back(u+1); int qr=query(qa[0].size(), qa[1].size(), qa[0].data(), qa[1].data()); if(!qr) continue; int cm=0; for(int k=0; k<i; ++k) { qa[0].clear(); qa[1].clear(); for(int j=0; j<cci; ++j) if((j&((1<<(k+1))-1))==cm) for(int u : ccs[j]) qa[j>>i&1].push_back(u+1); qr=query(qa[0].size(), qa[1].size(), qa[0].data(), qa[1].data()); if(!qr) cm|=1<<k; } qa[0].clear(); qa[1].clear(); for(int j=0; j<cci; ++j) if((j&((1<<i)-1))==cm) for(int u : ccs[j]) qa[j>>i&1].push_back(u+1); for(int j=0; j<2; ++j) { while(qa[j].size()>1) { qr=query(qa[j].size()/2, qa[j^1].size(), qa[j].data(), qa[j^1].data()); if(qr) qa[j].erase(qa[j].begin()+qa[j].size()/2, qa[j].end()); else qa[j].erase(qa[j].begin(), qa[j].begin()+qa[j].size()/2); } } int u=qa[0][0], v=qa[1][0]; setRoad(u, v); adj[u-1].push_back(v-1); adj[v-1].push_back(u-1); break; } memset(vis, 0, n); while(cci) ccs[--cci].clear(); } } /* int main() { int n; cin >> n; run(n); } //*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...