Submission #62120

#TimeUsernameProblemLanguageResultExecution timeMemory
62120bazsi700ICC (CEOI16_icc)C++14
100 / 100
873 ms1388 KiB
#include <bits/stdc++.h> #include "icc.h" using namespace std; #define MOD 1000000007 #define ll long long int #define vi vector<int> #define vii vector< vector<int> > #define PI 3.1415926535897932384626433832795 #define INF 9223372036854775807LL //13:22 int root[105]; set<pair<int,int> > noedge; int findroot(int x) { if(root[x] != x) { root[x] = findroot(root[x]); } return root[x]; } void join(int a, int b) { if(rand()%2) { root[findroot(a)] = findroot(b); } else { root[findroot(b)] = findroot(a); } } int queryy(int as, int bs, int a[], int b[]) { bool check = false; for(int i = 0; i < as; i++) { if(check) { break; } for(int j = 0; j < bs; j++) { if(noedge.count({a[i],b[j]}) == 0) { check = true; break; } } } if(!check) { return 0; } int an = query(as,bs,a,b); if(an == 0) { for(int i = 0; i < as; i++) { for(int j = 0; j < bs; j++) { noedge.insert({a[i],b[j]}); noedge.insert({b[j],a[i]}); } } } return an; } void run(int n) { srand(124167323); for(int i = 1; i <= n; i++) { root[i] = i; } for(int i = 1; i < n; i++) { noedge.clear(); set<int> roots; vii inroot(n+1,vi()); for(int i = 1; i <= n; i++) { roots.insert(findroot(i)); inroot[root[i]].push_back(i); } int x,y; x = -1; y = -1; vector<int> root1; vector<int> root1gr; vector<int> root2; vector<int> root2gr; while(true) { root1.clear(); root2.clear(); root1gr.clear(); root2gr.clear(); int s1 = 0; int s2 = 0; for(int rt : roots) { if(rand()%2) { root1.push_back(rt); s1+= inroot[rt].size(); } else { root2.push_back(rt); s2+= inroot[rt].size(); } } if(root2.empty() || int(root1.size())-int(root2.size()) > (n-i)/2+1) { root2.push_back(root1[root1.size()-1]); root1.pop_back(); s1-= inroot[root2[0]].size(); s2+= inroot[root2[0]].size(); } if(root1.empty() || int(root2.size())-int(root1.size()) > (n-i)/2+1) { root1.push_back(root2[root2.size()-1]); root2.pop_back(); s1+= inroot[root1[0]].size(); s2-= inroot[root1[0]].size(); } for(int rt : root1) { for(int el : inroot[rt]) { root1gr.push_back(el); } } for(int rt : root2) { for(int el : inroot[rt]) { root2gr.push_back(el); } } int a[root1gr.size()]; int b[root2gr.size()]; int ind = 0; for(int el : root1gr) { a[ind++] = el; } ind = 0; for(int el : root2gr) { b[ind++] = el; } int an = queryy(root1gr.size(),root2gr.size(),a,b); if(an == 1) { break; } } int ind = 0; vector<int> tempgr; for(int el : root2gr) { bool bad = true; for(int el2 : root1gr) { if(noedge.count({el,el2}) == 0) { bad = false; break; } } if(!bad) { tempgr.push_back(el); } } root2gr.clear(); for(int el : tempgr) { root2gr.push_back(el); } tempgr.clear(); for(int el : root1gr) { bool bad = true; for(int el2 : root2gr) { if(noedge.count({el,el2}) == 0) { bad = false; break; } } if(!bad) { tempgr.push_back(el); } } root1gr.clear(); for(int el : tempgr) { root1gr.push_back(el); } int b[root2gr.size()]; for(int el : root2gr) { b[ind++] = el; } vector<int> gr1; vector<int> gr2; ind = 0; for(int el : root1gr) { if(ind*2 < root1gr.size()) { gr1.push_back(el); } else { gr2.push_back(el); } ind++; } while(gr1.size() > 0 && gr2.size() > 0) { int a[gr1.size()]; ind = 0; for(int el : gr1) { a[ind++] = el; } int an = queryy(gr1.size(),root2gr.size(),a,b); if(an) { gr2.clear(); int ind = 0; for(int el : gr1) { if(ind*2 >= gr1.size()) { gr2.push_back(el); } ind++; } for(int tim = 0; tim < gr2.size(); tim++) { gr1.pop_back(); } } else { gr1.clear(); int ind = 0; for(int el : gr2) { if(ind*2 >= gr2.size()) { gr1.push_back(el); } ind++; } for(int tim = 0; tim < gr1.size(); tim++) { gr2.pop_back(); } } } if(gr1.empty()) { x = gr2[0]; } else { x = gr1[0]; } gr1.clear(); gr2.clear(); tempgr.clear(); for(int el : root2gr) { bool bad = true; if(noedge.count({el,x}) == 0) { bad = false; } if(!bad) { tempgr.push_back(el); } } root2gr.clear(); for(int el : tempgr) { root2gr.push_back(el); } ind = 0; for(int el : root2gr) { if(ind*2 < root2gr.size()) { gr1.push_back(el); } else { gr2.push_back(el); } ind++; } while(gr1.size() > 0 && gr2.size() > 0) { int bb[gr1.size()]; int a[1]; a[0] = x; ind = 0; for(int el : gr1) { bb[ind++] = el; } int an = queryy(1,gr1.size(),a,bb); if(an) { gr2.clear(); int ind = 0; for(int el : gr1) { if(ind*2 >= gr1.size()) { gr2.push_back(el); } ind++; } for(int tim = 0; tim < gr2.size(); tim++) { gr1.pop_back(); } } else { gr1.clear(); int ind = 0; for(int el : gr2) { if(ind*2 >= gr2.size()) { gr1.push_back(el); } ind++; } for(int tim = 0; tim < gr1.size(); tim++) { gr2.pop_back(); } } } if(gr1.empty()) { y = gr2[0]; } else { y = gr1[0]; } join(x,y); setRoad(x,y); } }

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:176:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind*2 < root1gr.size()) {
       ~~~~~~^~~~~~~~~~~~~~~~
icc.cpp:194:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(ind*2 >= gr1.size()) {
         ~~~~~~^~~~~~~~~~~~~
icc.cpp:199:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int tim = 0; tim < gr2.size(); tim++) {
                      ~~~~^~~~~~~~~~~~
icc.cpp:206:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(ind*2 >= gr2.size()) {
         ~~~~~~^~~~~~~~~~~~~
icc.cpp:211:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int tim = 0; tim < gr1.size(); tim++) {
                      ~~~~^~~~~~~~~~~~
icc.cpp:240:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind*2 < root2gr.size()) {
       ~~~~~~^~~~~~~~~~~~~~~~
icc.cpp:260:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(ind*2 >= gr1.size()) {
         ~~~~~~^~~~~~~~~~~~~
icc.cpp:265:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int tim = 0; tim < gr2.size(); tim++) {
                      ~~~~^~~~~~~~~~~~
icc.cpp:272:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(ind*2 >= gr2.size()) {
         ~~~~~~^~~~~~~~~~~~~
icc.cpp:277:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int tim = 0; tim < gr1.size(); tim++) {
                      ~~~~^~~~~~~~~~~~
#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...