제출 #1045587

#제출 시각아이디문제언어결과실행 시간메모리
1045587boyliguanhanSplit the Attractions (IOI19_split)C++17
100 / 100
147 ms25684 KiB
#include "split.h" #include<bits/stdc++.h> using namespace std; mt19937 rng(0); vector<int>adj[100100],adj2[100100]; bitset<100100>vis; int sz[100100],THEONE,treep[100100],dep[100100],fardest[100100]; vector<int>ans; int OK(int k,int a,int b,int c){ sz[k]=1; vis[k]=1; fardest[k]=dep[k]; for(auto i:adj[k]) if(!vis[i]){ treep[i]=k; dep[i]=dep[k]+1; if(OK(i,a,b,c)) return 1;sz[k]+=sz[i]; fardest[k]=min(fardest[k],fardest[i]); } else fardest[k]=min(fardest[k],dep[i]); if(a<=sz[k]&&sz[k]<=b+c) return THEONE=k,1; if(!THEONE&&sz[k]>a) THEONE=k; return 0; } void gendfstree(int n){ vis[n]=1; for(auto i:adj[n]) if(!vis[i]) gendfstree(i), adj2[n].push_back(i), adj2[i].push_back(n); } void docol(int n,int p,int &CC,int col){ if(!CC) return; ans[n]=col,CC--; for(auto x:adj2[n]) if(x-p)docol(x,n,CC,col); } void genans(int k,int a,int b,int c,int A,int B,int C){ for(auto&i:ans)i=C; vis.reset(); gendfstree(k); int n=a+b+c; if(sz[THEONE]>=b) swap(a,b),swap(A,B); docol(THEONE,treep[THEONE],a,A); docol(treep[THEONE],THEONE,b,B); assert(!a&&!b); } set<int> onesin; void docol2(int n,int &CC,int col){ if(!onesin.count(n))return; onesin.erase(n); if(!CC) return; ans[n]=col,CC--; for(auto x:adj[n]) docol2(x,CC,col); } void addto(int n,set<int>&st){ st.insert(n); for(auto i:adj[n]) if(treep[i]==n) addto(i,st); } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { ans.resize(n); vector<int> res; int m=p.size(); for(int i=0;i<m;i++) adj[p[i]].push_back(q[i]), adj[q[i]].push_back(p[i]); int A=1,B=2,C=3; if(a>b)swap(a,b),swap(A,B); if(b>c)swap(b,c),swap(B,C); if(a>b)swap(a,b),swap(A,B); vis.reset(); if(OK(0,a,b,c)) genans(0,a,b,c,A,B,C); else { set<int>in2,in1; int sz1=sz[THEONE]; addto(THEONE,in1); for(int i=0;i<n;i++) if(!in1.count(i)) in2.insert(i); for(auto x:adj[THEONE]) if(treep[x]==THEONE) if(fardest[x]<dep[THEONE]) { addto(x,in2); if(in2.size()>=a)break; } if(in2.size()<a)return ans; for(auto&i:ans)i=C; onesin=in2; for(auto i:in2) in1.erase(i); docol2(0,a,A); onesin=in1; docol2(THEONE,b,B); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'int OK(int, int, int, int)':
split.cpp:14:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   14 |   if(OK(i,a,b,c)) return 1;sz[k]+=sz[i];
      |   ^~
split.cpp:14:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   14 |   if(OK(i,a,b,c)) return 1;sz[k]+=sz[i];
      |                            ^~
split.cpp:19:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   19 |     if(!THEONE&&sz[k]>a)
      |     ^~
split.cpp:21:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |  return 0;
      |  ^~~~~~
split.cpp: In function 'void genans(int, int, int, int, int, int, int)':
split.cpp:40:6: warning: unused variable 'n' [-Wunused-variable]
   40 |  int n=a+b+c;
      |      ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:87:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |                     if(in2.size()>=a)break;
      |                        ~~~~~~~~~~^~~
split.cpp:89:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if(in2.size()<a)return ans;
      |            ~~~~~~~~~~^~
split.cpp:78:13: warning: unused variable 'sz1' [-Wunused-variable]
   78 |         int sz1=sz[THEONE];
      |             ^~~
#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...