제출 #749785

#제출 시각아이디문제언어결과실행 시간메모리
749785groguSplit the Attractions (IOI19_split)C++14
컴파일 에러
0 ms0 KiB
#include "split.h" #define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld double #define ll int #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define eb emplace_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define si(a) (ll)(a.size()) using namespace std; const ll maxn = 200005; ll n,m; vector<ll> g[maxn]; vector<ll> c[maxn]; vector<ll> e[maxn]; ll dsu[maxn],sz[maxn],tsz = 0; ll x,y,xid,yid; ll poc,col,colid; bool ok; ll sub[maxn]; ll par[maxn]; bool vis[maxn]; vector<ll> ans; void dfs(ll u,ll p){ sub[u] = 1; par[u] = p; vis[u] = 1; for(ll s : g[u]){ if(vis[s]) continue; dfs(s,u); e[u].pb(s); e[s].pb(u); sub[u]+=sub[s]; } if(sub[u]>=x&&n-sub[u]>=y){ poc = u; col = x; colid = xid; ok = 1; } if(sub[u]>=y&&n-sub[u]>=x){ poc = u; col = y; colid = yid; ok = 1; } } void dfscol(ll u,ll p,ll col,ll &z){ if(z){ ans[u] = col; z--; } for(ll s : e[u]){ if(s==p) continue; dfscol(s,u,col,z); } } ll cen(ll u,ll p){ for(ll s : e[u]){ if(s==p) continue; if(sub[s]*2>n) return cen(s,u); } return u; } void dfscomp(ll u,ll p){ dsu[u] = tsz; sz[tsz]++; for(ll s : e[u]){ if(s==p) continue; dfscomp(s,u); } } ll curcnt = 0; ll use[maxn]; void dfscheck(ll u,ll st){ curcnt+=sz[u]; vis[u] = 1; if(curcnt>=x){ use[u] = st; ok = 1; return; } for(ll s : c[u]){ if(vis[s]) continue; dfscheck(s,st); if(ok) return; } } void dfscol2(ll u,ll col,ll &z,ll st){ ans[u] = col; for(ll s : g[u]) if(use[dsu[s]]==st&&!ans[s]) dfscol2(s,col,z); } void dfscol3(ll u,ll col,ll &z){ if(z) ans[u] = col,z--; else return; for(ll s : e[u]) if(!ans[dsu[s]]) dfscol3(s,col,z); } vector<int> find_split(int N, int A,int B,int C, vector<int> p, vector<int> q) { n = N; m = si(p); vector<pll> v; v.pb({A,1}); v.pb({B,2}); v.pb({C,3}); sort(all(v)); x = v[0].fi; xid = v[0].sc; y = v[1].fi; yid = v[1].sc; for(ll i = 1;i<=m;i++){ ll x = p[i-1] + 1; ll y = q[i-1] + 1; g[x].pb(y); g[y].pb(x); } dfs(1,1); ans.resize(n+1); if(ok){ ll tmp = col; dfscol(poc,par[poc],colid,col); tmp^=y; tmp^=x; dfscol(par[poc],poc,colid^xid^yid,tmp); for(ll i = 1;i<=n;i++){ if(ans[i]==0) ans[i] = v[2].sc; } reverse(all(ans)); ans.popb(); reverse(all(ans)); return ans; } ll root = cen(1,1); for(ll j : e[root]){ ++tsz; dfscomp(j,root); } for(ll i = 1;i<=n;i++){ if(i==root) continue; for(ll j : g[i]){ if(j==root) continue; c[dsu[i]].pb(dsu[j]); c[dsu[j]].pb(dsu[i]); } } fill(vis,vis+1+n,0); for(ll i = 1;i<=tsz;i++){ if(vis[i]) continue; curcnt = 0; dfscheck(i,i); if(ok){poc = i; break;} } if(!ok){ans.popb(); return ans;} for(ll i = 1;i<=n;i++){ if(dsu[i]==poc){ dfscol2(i,xid,x,poc); break; } } dfscol3(root,yid,y); for(ll i = 1;i<=n;i++){ if(ans[i]==0) ans[i] = v[2].sc; } reverse(all(ans)); ans.popb(); reverse(all(ans)); return ans; } /** 6 5 2 2 2 0 1 0 2 0 3 0 4 0 5 9 10 4 2 3 0 1 0 2 0 3 0 4 0 6 0 8 1 7 3 7 4 5 5 6 **/ #include "split.h" #define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld double #define ll int #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define eb emplace_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define si(a) (ll)(a.size()) using namespace std; const ll maxn = 200005; ll n,m; vector<ll> g[maxn]; vector<ll> c[maxn]; vector<ll> e[maxn]; ll dsu[maxn],sz[maxn],tsz = 0; ll x,y,xid,yid; ll poc,col,colid; bool ok; ll sub[maxn]; ll par[maxn]; bool vis[maxn]; vector<ll> ans; void dfs(ll u,ll p){ sub[u] = 1; par[u] = p; vis[u] = 1; for(ll s : g[u]){ if(vis[s]) continue; dfs(s,u); e[u].pb(s); e[s].pb(u); sub[u]+=sub[s]; } if(sub[u]>=x&&n-sub[u]>=y){ poc = u; col = x; colid = xid; ok = 1; } if(sub[u]>=y&&n-sub[u]>=x){ poc = u; col = y; colid = yid; ok = 1; } } void dfscol(ll u,ll p,ll col,ll &z){ if(z){ ans[u] = col; z--; } for(ll s : e[u]){ if(s==p) continue; dfscol(s,u,col,z); } } ll cen(ll u,ll p){ for(ll s : e[u]){ if(s==p) continue; if(sub[s]*2>n) return cen(s,u); } return u; } void dfscomp(ll u,ll p){ dsu[u] = tsz; sz[tsz]++; for(ll s : e[u]){ if(s==p) continue; dfscomp(s,u); } } ll curcnt = 0; ll use[maxn]; void dfscheck(ll u,ll st){ curcnt+=sz[u]; vis[u] = 1; if(curcnt>=x){ use[u] = st; ok = 1; return; } for(ll s : c[u]){ if(vis[s]) continue; dfscheck(s,st); if(ok) return; } } void dfscol2(ll u,ll col,ll &z,ll st){ ans[u] = col; for(ll s : g[u]) if(use[dsu[s]]==st&&!ans[s]) dfscol2(s,col,z); } void dfscol3(ll u,ll col,ll &z){ if(z) ans[u] = col,z--; else return; for(ll s : e[u]) if(!ans[dsu[s]]) dfscol3(s,col,z); } vector<int> find_split(int N, int A,int B,int C, vector<int> p, vector<int> q) { n = N; m = si(p); vector<pll> v; v.pb({A,1}); v.pb({B,2}); v.pb({C,3}); sort(all(v)); x = v[0].fi; xid = v[0].sc; y = v[1].fi; yid = v[1].sc; for(ll i = 1;i<=m;i++){ ll x = p[i-1] + 1; ll y = q[i-1] + 1; g[x].pb(y); g[y].pb(x); } dfs(1,1); ans.resize(n+1); if(ok){ ll tmp = col; dfscol(poc,par[poc],colid,col); tmp^=y; tmp^=x; dfscol(par[poc],poc,colid^xid^yid,tmp); for(ll i = 1;i<=n;i++){ if(ans[i]==0) ans[i] = v[2].sc; } reverse(all(ans)); ans.popb(); reverse(all(ans)); return ans; } ll root = cen(1,1); for(ll j : e[root]){ ++tsz; dfscomp(j,root); } for(ll i = 1;i<=n;i++){ if(i==root) continue; for(ll j : g[i]){ if(j==root) continue; c[dsu[i]].pb(dsu[j]); c[dsu[j]].pb(dsu[i]); } } fill(vis,vis+1+n,0); for(ll i = 1;i<=tsz;i++){ if(vis[i]) continue; curcnt = 0; dfscheck(i,i); if(ok){poc = i; break;} } if(!ok){ans.popb(); return ans;} for(ll i = 1;i<=n;i++){ if(dsu[i]==poc){ dfscol2(i,xid,x,poc); break; } } dfscol3(root,yid,y); for(ll i = 1;i<=n;i++){ if(ans[i]==0) ans[i] = v[2].sc; } reverse(all(ans)); ans.popb(); reverse(all(ans)); return ans; } /** 6 5 2 2 2 0 1 0 2 0 3 0 4 0 5 9 10 4 2 3 0 1 0 2 0 3 0 4 0 6 0 8 1 7 3 7 4 5 5 6 **/

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

split.cpp: In function 'void dfscol2(int, int, int&, int)':
split.cpp:99:66: error: too few arguments to function 'void dfscol2(int, int, int&, int)'
   99 |     for(ll s : g[u]) if(use[dsu[s]]==st&&!ans[s]) dfscol2(s,col,z);
      |                                                                  ^
split.cpp:97:6: note: declared here
   97 | void dfscol2(ll u,ll col,ll &z,ll st){
      |      ^~~~~~~
split.cpp: At global scope:
split.cpp:218:10: error: redefinition of 'const int maxn'
  218 | const ll maxn = 200005;
      |          ^~~~
split.cpp:25:10: note: 'const int maxn' previously defined here
   25 | const ll maxn = 200005;
      |          ^~~~
split.cpp:219:4: error: redefinition of 'int n'
  219 | ll n,m;
      |    ^
split.cpp:26:4: note: 'int n' previously declared here
   26 | ll n,m;
      |    ^
split.cpp:219:6: error: redefinition of 'int m'
  219 | ll n,m;
      |      ^
split.cpp:26:6: note: 'int m' previously declared here
   26 | ll n,m;
      |      ^
split.cpp:220:12: error: redefinition of 'std::vector<int> g [200005]'
  220 | vector<ll> g[maxn];
      |            ^
split.cpp:27:12: note: 'std::vector<int> g [200005]' previously declared here
   27 | vector<ll> g[maxn];
      |            ^
split.cpp:221:12: error: redefinition of 'std::vector<int> c [200005]'
  221 | vector<ll> c[maxn];
      |            ^
split.cpp:28:12: note: 'std::vector<int> c [200005]' previously declared here
   28 | vector<ll> c[maxn];
      |            ^
split.cpp:222:12: error: redefinition of 'std::vector<int> e [200005]'
  222 | vector<ll> e[maxn];
      |            ^
split.cpp:29:12: note: 'std::vector<int> e [200005]' previously declared here
   29 | vector<ll> e[maxn];
      |            ^
split.cpp:223:4: error: redefinition of 'int dsu [200005]'
  223 | ll dsu[maxn],sz[maxn],tsz = 0;
      |    ^~~
split.cpp:30:4: note: 'int dsu [200005]' previously declared here
   30 | ll dsu[maxn],sz[maxn],tsz = 0;
      |    ^~~
split.cpp:223:14: error: redefinition of 'int sz [200005]'
  223 | ll dsu[maxn],sz[maxn],tsz = 0;
      |              ^~
split.cpp:30:14: note: 'int sz [200005]' previously declared here
   30 | ll dsu[maxn],sz[maxn],tsz = 0;
      |              ^~
split.cpp:223:23: error: redefinition of 'int tsz'
  223 | ll dsu[maxn],sz[maxn],tsz = 0;
      |                       ^~~
split.cpp:30:23: note: 'int tsz' previously defined here
   30 | ll dsu[maxn],sz[maxn],tsz = 0;
      |                       ^~~
split.cpp:224:4: error: redefinition of 'int x'
  224 | ll x,y,xid,yid;
      |    ^
split.cpp:31:4: note: 'int x' previously declared here
   31 | ll x,y,xid,yid;
      |    ^
split.cpp:224:6: error: redefinition of 'int y'
  224 | ll x,y,xid,yid;
      |      ^
split.cpp:31:6: note: 'int y' previously declared here
   31 | ll x,y,xid,yid;
      |      ^
split.cpp:224:8: error: redefinition of 'int xid'
  224 | ll x,y,xid,yid;
      |        ^~~
split.cpp:31:8: note: 'int xid' previously declared here
   31 | ll x,y,xid,yid;
      |        ^~~
split.cpp:224:12: error: redefinition of 'int yid'
  224 | ll x,y,xid,yid;
      |            ^~~
split.cpp:31:12: note: 'int yid' previously declared here
   31 | ll x,y,xid,yid;
      |            ^~~
split.cpp:225:4: error: redefinition of 'int poc'
  225 | ll poc,col,colid;
      |    ^~~
split.cpp:32:4: note: 'int poc' previously declared here
   32 | ll poc,col,colid;
      |    ^~~
split.cpp:225:8: error: redefinition of 'int col'
  225 | ll poc,col,colid;
      |        ^~~
split.cpp:32:8: note: 'int col' previously declared here
   32 | ll poc,col,colid;
      |        ^~~
split.cpp:225:12: error: redefinition of 'int colid'
  225 | ll poc,col,colid;
      |            ^~~~~
split.cpp:32:12: note: 'int colid' previously declared here
   32 | ll poc,col,colid;
      |            ^~~~~
split.cpp:226:6: error: redefinition of 'bool ok'
  226 | bool ok;
      |      ^~
split.cpp:33:6: note: 'bool ok' previously declared here
   33 | bool ok;
      |      ^~
split.cpp:227:4: error: redefinition of 'int sub [200005]'
  227 | ll sub[maxn];
      |    ^~~
split.cpp:34:4: note: 'int sub [200005]' previously declared here
   34 | ll sub[maxn];
      |    ^~~
split.cpp:228:4: error: redefinition of 'int par [200005]'
  228 | ll par[maxn];
      |    ^~~
split.cpp:35:4: note: 'int par [200005]' previously declared here
   35 | ll par[maxn];
      |    ^~~
split.cpp:229:6: error: redefinition of 'bool vis [200005]'
  229 | bool vis[maxn];
      |      ^~~
split.cpp:36:6: note: 'bool vis [200005]' previously declared here
   36 | bool vis[maxn];
      |      ^~~
split.cpp:230:12: error: redefinition of 'std::vector<int> ans'
  230 | vector<ll> ans;
      |            ^~~
split.cpp:37:12: note: 'std::vector<int> ans' previously declared here
   37 | vector<ll> ans;
      |            ^~~
split.cpp:231:6: error: redefinition of 'void dfs(int, int)'
  231 | void dfs(ll u,ll p){
      |      ^~~
split.cpp:38:6: note: 'void dfs(int, int)' previously defined here
   38 | void dfs(ll u,ll p){
      |      ^~~
split.cpp:249:6: error: redefinition of 'void dfscol(int, int, int, int&)'
  249 | void dfscol(ll u,ll p,ll col,ll &z){
      |      ^~~~~~
split.cpp:56:6: note: 'void dfscol(int, int, int, int&)' previously defined here
   56 | void dfscol(ll u,ll p,ll col,ll &z){
      |      ^~~~~~
split.cpp:259:4: error: redefinition of 'int cen(int, int)'
  259 | ll cen(ll u,ll p){
      |    ^~~
split.cpp:66:4: note: 'int cen(int, int)' previously defined here
   66 | ll cen(ll u,ll p){
      |    ^~~
split.cpp:266:6: error: redefinition of 'void dfscomp(int, int)'
  266 | void dfscomp(ll u,ll p){
      |      ^~~~~~~
split.cpp:73:6: note: 'void dfscomp(int, int)' previously defined here
   73 | void dfscomp(ll u,ll p){
      |      ^~~~~~~
split.cpp:274:4: error: redefinition of 'int curcnt'
  274 | ll curcnt = 0;
      |    ^~~~~~
split.cpp:81:4: note: 'int curcnt' previously defined here
   81 | ll curcnt = 0;
      |    ^~~~~~
split.cpp:275:4: error: redefinition of 'int use [200005]'
  275 | ll use[maxn];
      |    ^~~
split.cpp:82:4: note: 'int use [200005]' previously declared here
   82 | ll use[maxn];
      |    ^~~
split.cpp:276:6: error: redefinition of 'void dfscheck(int, int)'
  276 | void dfscheck(ll u,ll st){
      |      ^~~~~~~~
split.cpp:83:6: note: 'void dfscheck(int, int)' previously defined here
   83 | void dfscheck(ll u,ll st){
      |      ^~~~~~~~
split.cpp:290:6: error: redefinition of 'void dfscol2(int, int, int&, int)'
  290 | void dfscol2(ll u,ll col,ll &z,ll st){
      |      ^~~~~~~
split.cpp:97:6: note: 'void dfscol2(int, int, int&, int)' previously defined here
   97 | void dfscol2(ll u,ll col,ll &z,ll st){
      |      ^~~~~~~
split.cpp: In function 'void dfscol2(int, int, int&, int)':
split.cpp:292:66: error: too few arguments to function 'void dfscol2(int, int, int&, int)'
  292 |     for(ll s : g[u]) if(use[dsu[s]]==st&&!ans[s]) dfscol2(s,col,z);
      |                                                                  ^
split.cpp:97:6: note: declared here
   97 | void dfscol2(ll u,ll col,ll &z,ll st){
      |      ^~~~~~~
split.cpp: At global scope:
split.cpp:294:6: error: redefinition of 'void dfscol3(int, int, int&)'
  294 | void dfscol3(ll u,ll col,ll &z){
      |      ^~~~~~~
split.cpp:101:6: note: 'void dfscol3(int, int, int&)' previously defined here
  101 | void dfscol3(ll u,ll col,ll &z){
      |      ^~~~~~~
split.cpp:299:13: error: redefinition of 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)'
  299 | vector<int> find_split(int N, int A,int B,int C, vector<int> p, vector<int> q) {
      |             ^~~~~~~~~~
split.cpp:106:13: note: 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)' previously defined here
  106 | vector<int> find_split(int N, int A,int B,int C, vector<int> p, vector<int> q) {
      |             ^~~~~~~~~~