Submission #858523

#TimeUsernameProblemLanguageResultExecution timeMemory
858523Tenis0206ICC (CEOI16_icc)C++11
100 / 100
103 ms640 KiB
#include <bits/stdc++.h> #ifndef home #include "icc.h" #endif // home using namespace std; const int nmax = 100; #ifdef home pair<int,int> e[nmax + 5]; void output(string msg) { cout<<msg<<'\n'; exit(0); } int cnt = 1; int query(int sza, int szb, int a[], int b[]) { bool ok = false; for(int i=0;i<sza;i++) { for(int j=0;j<szb;j++) { for(int nr=1;nr<=cnt;nr++) { if(e[nr].first==a[i] && e[nr].second==b[j]) { ok = true; break; } if(e[nr].first==b[j] && e[nr].second==a[i]) { ok = true; break; } } } } return ok; } void setRoad(int a, int b) { bool ok = false; if(a==e[cnt].first && b==e[cnt].second) { ok = true; } if(a==e[cnt].second && b==e[cnt].first) { ok = true; } if(!ok) { output("Bad edge"); } ++cnt; } #endif // home int n; int a[nmax + 5], b[nmax + 5]; int vst[nmax + 5]; int t[nmax + 5]; vector<int> l[nmax + 5]; mt19937 my_rand(time(NULL)); int my_rand_val(int x) { return my_rand() % x; } int rep(int x) { if(t[x]==x) { return x; } return rep(t[x]); } void uneste(int x, int y) { x = rep(x); y = rep(y); if(x==y) { return; } if(l[x].size() > l[y].size()) { for(auto it : l[y]) { l[x].push_back(it); } l[y].clear(); t[y] = x; } else { for(auto it : l[x]) { l[y].push_back(it); } l[x].clear(); t[x] = y; } } pair<int,int> find_dif(int nra, int nrb) { random_shuffle(a,a+nra,my_rand_val); random_shuffle(b,b+nrb,my_rand_val); int val_a = 0, val_b = 0; int st = 1; int dr = nra; while(st<dr) { int mij = (st + dr) >> 1; int nrv = 0; for(int i=st;i<=mij;i++) { vst[nrv++] = a[i - 1]; } int ok = query(nrv, nrb, vst, b); if(ok) { dr = mij; } else { st = mij + 1; } } val_a = a[st - 1]; st = 1; dr = nrb; while(st<dr) { int mij = (st + dr) >> 1; int nrv = 0; for(int i=st;i<=mij;i++) { vst[nrv++] = b[i - 1]; } int ok = query(nrv, nra, vst, a); if(ok) { dr = mij; } else { st = mij + 1; } } val_b = b[st - 1]; return {val_a, val_b}; } void find_new_edge() { vector<int> c; for(int i=1;i<=n;i++) { if(rep(i)==i) { c.push_back(i); } } random_shuffle(c.begin(),c.end(),my_rand_val); pair<int,int> rez = {0,0}; for(int bit=0;(1<<bit)<c.size();bit++) { int nra = 0, nrb = 0; for(int i=0;i<c.size();i++) { if((i & (1<<bit)) == 0) { for(auto it : l[c[i]]) { a[nra++] = it; } } else { for(auto it : l[c[i]]) { b[nrb++] = it; } } } int ok = query(nra, nrb, a, b); if(ok) { rez = find_dif(nra, nrb); break; } } setRoad(rez.first,rez.second); uneste(rez.first, rez.second); } void run(int N) { srand(time(NULL)); n = N; for(int i=1;i<=n;i++) { t[i] = i; l[i].push_back(i); } for(int i=1;i<n;i++) { find_new_edge(); } } #ifdef home int main() { freopen("nr.in","r",stdin); freopen("nr.out","w",stdout); int nn; cin>>nn; for(int i=1;i<nn;i++) { int x,y; cin>>x>>y; e[i] = {x,y}; } run(nn); output("OK"); return 0; } #endif // home

Compilation message (stderr)

icc.cpp: In function 'void find_new_edge()':
icc.cpp:183:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for(int bit=0;(1<<bit)<c.size();bit++)
      |                   ~~~~~~~~^~~~~~~~~
icc.cpp:186:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |         for(int i=0;i<c.size();i++)
      |                     ~^~~~~~~~~
#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...