Submission #879187

#TimeUsernameProblemLanguageResultExecution timeMemory
879187andrei_boacaSplit the Attractions (IOI19_split)C++17
40 / 100
470 ms29896 KiB
#include "split.h" #include <bits/stdc++.h> //#include "grader.cpp" //#pragma GCC optimize ("Ofast") //#pragma GCC optimize ("fast-math") //#pragma GCC optimize ("unroll-loops") using namespace std; typedef pair<int,int> pii; mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); int n,m; int take[5],ord[5]; vector<int> sol; bool byval(int a,int b) { return take[a]<take[b]; } vector<int> muchii[100005],edges[100005]; vector<int> dsu[100005]; int comp[100005]; vector<pii> g; vector<int> linie; int par[100005]; bool use[100005]; vector<int> nodes; int nr[100005]; void dsu_merge(int c1,int c2) { if(dsu[c1].size()<dsu[c2].size()) swap(c1,c2); for(int i:dsu[c2]) { comp[i]=c1; dsu[c1].push_back(i); } dsu[c2].clear(); } void dfslin(int nod) { linie.push_back(nod); for(int i:muchii[nod]) if(i!=par[nod]) { par[i]=nod; dfslin(i); } } void dfsmake(int nod) { nodes.push_back(nod); use[nod]=1; for(int i:muchii[nod]) if(!use[i]) dfsmake(i); } void dfs(int nod) { nr[nod]=1; for(int i:muchii[nod]) if(i!=par[nod]) { par[i]=nod; dfs(i); nr[nod]+=nr[i]; } } int root=0; void make(int nod) { use[nod]=1; for(int i:edges[nod]) if(!use[i]) { muchii[i].push_back(nod); muchii[nod].push_back(i); make(i); } } void build() { for(int i=0;i<n;i++) { use[i]=0; muchii[i].clear(); muchii[i].shrink_to_fit(); nr[i]=0; par[i]=-1; } make(root); for(int i=0;i<n;i++) use[i]=0; } vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) { n=N; take[1]=A; take[2]=B; take[3]=C; ord[1]=1; ord[2]=2; ord[3]=3; sort(ord+1,ord+4,byval); sol.resize(n); m=p.size(); for(int i=0;i<n;i++) { par[i]=-1; comp[i]=i+1; dsu[i+1].push_back(i); } for(int i=0;i<p.size();i++) { int a=p[i]; int b=q[i]; edges[a].push_back(b); edges[b].push_back(a); g.push_back({a,b}); if(comp[a]!=comp[b]) { muchii[a].push_back(b); muchii[b].push_back(a); dsu_merge(comp[a],comp[b]); } } bool sub1=1; for(int i=0;i<n;i++) if(muchii[i].size()>2) sub1=0; if(sub1) { int root=0; for(int i=0;i<n;i++) { assert(muchii[i].size()>=1); if(muchii[i].size()==1) { root=i; break; } } dfslin(root); //assert(linie.size()==n); for(int i=0;i<n;i++) { if(i<A) sol[linie[i]]=1; else if(i<A+B) sol[linie[i]]=2; else sol[linie[i]]=3; } return sol; } if(A==1) { int who=0; for(int i=0;i<n;i++) if(muchii[i].size()==1) { who=i; break; } use[who]=1; sol[who]=1; dfsmake(muchii[who][0]); for(int i=0;i<nodes.size();i++) { if(i<B) sol[nodes[i]]=2; else sol[nodes[i]]=3; } return sol; } dfs(0); int x=-1,y=-1; for(int i=1;i<n;i++) { if(min(nr[i],n-nr[i])>=take[ord[1]]&&max(nr[i],n-nr[i])>=take[ord[2]]) { x=i; y=par[i]; } } if(x==-1) { bool found=0; if(n<=2500) { for(int r=n-1;r>-0&&!found;r--) { root=r; build(); dfs(root); for(int i=0;i<n&&!found;i++) if(i!=root) if(min(nr[i],n-nr[i])>=take[ord[1]]&&max(nr[i],n-nr[i])>=take[ord[2]]) { x=i; y=par[i]; found=1; } } } if(!found) return sol; } if(nr[x]>n-nr[x]) swap(x,y); use[x]=1; use[y]=1; nodes.clear(); dfsmake(x); sol[x]=ord[1]; for(int i=1;i<nodes.size();i++) { if(i<=take[ord[1]]-1) sol[nodes[i]]=ord[1]; else sol[nodes[i]]=ord[3]; } nodes.clear(); dfsmake(y); sol[y]=ord[2]; for(int i=1;i<nodes.size();i++) { if(i<=take[ord[2]]-1) sol[nodes[i]]=ord[2]; else sol[nodes[i]]=ord[3]; } return sol; }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=0;i<p.size();i++)
      |                 ~^~~~~~~~~
split.cpp:165:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for(int i=0;i<nodes.size();i++)
      |                     ~^~~~~~~~~~~~~
split.cpp:214:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |     for(int i=1;i<nodes.size();i++)
      |                 ~^~~~~~~~~~~~~
split.cpp:225:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for(int i=1;i<nodes.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...