제출 #836678

#제출 시각아이디문제언어결과실행 시간메모리
836678AntekbSplit the Attractions (IOI19_split)C++17
22 / 100
125 ms32652 KiB
#include<bits/stdc++.h> #include "split.h" #define st first #define nd second #define pb push_back #define eb emplace_back #define pp pop_back #define mp make_pair #define all(x) (x).begin(), (x).end() using namespace std; using pii = pair<int, int>; using vi = vector<int>; using vii = vector<pii>; using ll = long long; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); void debug(){cerr<<"\n";} template<typename H, typename... T> void debug(H h, T... t){ cerr<<h; if(sizeof...(t))cerr<<", "; debug(t...); } #define deb(x...) cerr<<#x<<" = ";debug(x); const int N=1e5+5; vi E[N], E2[N], E3[N]; vi kto[N]; int pre[N], lo[N], par[N], czy_art[N], czy_root[N], bcc[N], roz[N], siz[N]; int n; int cent; int wsk=1; void dfs(int v){ lo[v]=pre[v]=wsk++; for(int u:E[v]){ if(!pre[u]){ par[u]=v; dfs(u); lo[v]=min(lo[v], lo[u]); } else if(u!=par[v]){ lo[v]=min(lo[v], pre[u]); } } if(par[v]!=-1 && lo[v]>=pre[par[v]]){ //deb(v, par[v]); czy_art[par[v]]=1; } } void color(int v, int c){ if(v==c)czy_root[v]=1; bcc[v]=c; roz[c]++; kto[c].pb(v); for(int u:E[v]){ if(v==par[u]){ if(!czy_art[u] && !czy_art[v])color(u, c); else color(u, u); } } } void dfs_cent(int v){ siz[v]=roz[v]; bool czy=1; for(int u:E2[v]){ if(!siz[u]){ E3[u].pb(v); E3[v].pb(u); dfs_cent(u); siz[v]+=siz[u]; if(2*siz[u]>n)czy=0; } } if(czy && 2*(n-siz[v])<=n){ cent=v; } } void dfs_sz(int v){ siz[v]=roz[v]; for(int u:E3[v]){ if(u!=par[v]){ par[u]=v; dfs_sz(u); siz[v]+=siz[u]; } } } vi find(int a, vi dozw){ //deb(a, dozw[0], dozw[1], dozw[2]); vi V; for(int i=0; i<n; i++){ if(dozw[i]){ dozw[i]=0; V.pb(i); break; } } for(int i=0; i<V.size(); i++){ int v=V[i]; //deb(v); for(int u:E[v]){ if(dozw[u]){ dozw[u]=0; V.pb(u); } } } for(int i=0; i<n; i++){ if(dozw[i])assert(false); } //if(V.size()<a)return V; //assert(V.size()>=a); V.resize(a); return V; } vi get_subtree(int u){ vi uzy(n); vi V; V.pb(u); uzy[u]=1; for(int i=0; i<V.size(); i++){ int v=V[i]; for(int uu:E3[v]){ if(par[uu]==v){ uzy[uu]=1; V.pb(uu); } } } int t=V.size(); for(int i=0; i<t; i++){ int v=V[i]; for(int uu:kto[v]){ //deb(uu); if(!uzy[uu]){ V.pb(uu); uzy[uu]=1; } } } return V; } void dfs2(int v){ lo[v]=pre[v]=wsk++; for(int u:E2[v]){ if(!pre[u]){ par[u]=v; dfs2(u); lo[v]=min(lo[v], lo[u]); } else if(u!=par[v]){ lo[v]=min(lo[v], pre[u]); } } if(par[v]!=-1 && lo[v]>=pre[par[v]]){ czy_art[par[v]]=1; } } vector<int> find_split(int _n, int a, int b, int c, vector<int> uu, vector<int> vv) { n=_n; for(int i=0; i<uu.size(); i++){ E[uu[i]].pb(vv[i]); E[vv[i]].pb(uu[i]); } par[0]=-1; dfs(0); int ile=0; for(int u:E[0]){ if(par[u]==0)ile++; } czy_art[0]=(ile!=1); for(int i=0; i<n; i++){ //deb(i, par[i], czy_art[i]); } color(0, 0); for(int i=0; i<n; i++){ pre[i]=0; for(int j:E[i]){ if(bcc[i]!=bcc[j])E2[bcc[i]].pb(bcc[j]); } //deb(i, bcc[i]); } for(int i=0; i<n; i++){ if(!czy_root[i])continue; sort(all(E2[i])); E2[i].resize(unique(all(E2[i]))-E2[i].begin()); //deb(i, E2[i].size()); for(int u:E2[i]){ //deb(u); } } cent=-5; dfs_cent(0); par[cent]=-1; dfs_sz(cent); deb(cent); for(int i=0; i<n; i++){ if(czy_root[i]){ //deb(i, roz[i], siz[i]) } } int A=min({a, b, c}), C=max({a, b, c}); int B=n-A-C; bool bb=0; vector<int> res(n, 0); vi X,Y,Z; for(int u:E3[cent]){ if(siz[u]>=A){ //assert(siz[u]*2<=n); //assert(n-siz[u]>=B); deb(u, siz[u], A); vi V=get_subtree(u); //assert(n<=5000); vi dozw(n); for(int i:V){ dozw[i]=1; } X=find(A, dozw); //assert(X.size()==A); for(int i:X){ //deb(i); } for(int &i:dozw)i^=1; Y=find(B, dozw); //assert(Y.size()==B); for(int &i:dozw)i=0; for(int i:Y){ dozw[i]=1; } for(int i:X){ dozw[i]=1; } for(int i=0; i<n; i++){ if(!dozw[i])Z.pb(i); } bb=1; break; } } deb("a"); if(!bb){ if(roz[0]==1)return res; //if(n>=5000)assert(false); for(int u:E3[cent]){ roz[u]=siz[u]; czy_root[u]=1; kto[u]=get_subtree(u); assert(siz[u]==kto[u].size()); roz[u]=siz[u]; for(int v:kto[u])bcc[v]=u, czy_root[v]=0; } for(int u:kto[0]){ if(u!=0){ kto[u]={u}; bcc[u]=u; roz[u]=1; czy_root[u]=1; } } kto[0]={0}; roz[0]=1; for(int i=0; i<n; i++)E2[i].clear(); for(int i=0; i<n; i++){ pre[i]=0; for(int j:E[i]){ if(bcc[i]!=bcc[j])E2[bcc[i]].pb(bcc[j]); } //deb(i, bcc[i]); } for(int i=0; i<n; i++){ if(!czy_root[i])continue; sort(all(E2[i])); E2[i].resize(unique(all(E2[i]))-E2[i].begin()); } for(int i=0; i<n; i++){ //deb(i, bcc[i], czy_root[i], kto[i].size(), E2[i].size()) if(czy_root[i]){ for(int u:E2[i]){ //deb(u); } } } vi V; for(int i=0; i<n; i++){ if(czy_root[i])V.pb(i); } vi czy_cand(V.size(), 1); vi mamy; vi cand; int sum=0; cand.pb(0); czy_cand[0]=0; //assert(A==1); while(sum<A){ for(int i:V)pre[i]=0, czy_art[i]=0; for(int i:mamy)pre[i]=1e9; wsk=1; bb=0; for(int i:V){ if(!pre[i]){ par[i]=-1; dfs2(i); bb=1; break; } } assert(bb); bb=0; ile=0; for(int u:E[0]){ if(par[u]==0)ile++; } czy_art[0]=(ile!=1); for(int &i:cand){ if(1){ mamy.pb(i); sum+=roz[i]; for(int u:E2[i]){ if(czy_cand[u]){ czy_cand[u]=0; cand.pb(u); } } bb=1; swap(i, cand.back()); cand.pp(); break; } } assert(bb); } //assert(mamy.size()==1); vi dozw(n); for(int i:mamy){ for(int j:kto[i]){ dozw[j]=1; } } //X=find(A, dozw); for(int i:X){ //deb(i); } for(int &i:dozw)i^=1; Y=find(B, dozw); for(int &i:dozw)i=0; for(int i:Y){ dozw[i]=1; } for(int i:X){ dozw[i]=1; } for(int i=0; i<n; i++){ if(!dozw[i])Z.pb(i); } } if(A!=a){ swap(A, B); swap(X, Y); } if(A!=a){ swap(A, C); swap(X, Z); } if(B!=b){ swap(C, B); swap(Z, Y); } for(int i:X)res[i]=1; for(int i:Y)res[i]=2; for(int i:Z)res[i]=3; return res; }

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

split.cpp: In function 'vi find(int, vi)':
split.cpp:100:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
split.cpp: In function 'vi get_subtree(int)':
split.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |    for(int i=0; i<V.size(); i++){
      |                 ~^~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:163:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |  for(int i=0; i<uu.size(); i++){
      |               ~^~~~~~~~~~
split.cpp:190:11: warning: unused variable 'u' [-Wunused-variable]
  190 |   for(int u:E2[i]){
      |           ^
split.cpp:222:12: warning: unused variable 'i' [-Wunused-variable]
  222 |    for(int i:X){
      |            ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from split.cpp:1:
split.cpp:250:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |    assert(siz[u]==kto[u].size());
      |           ~~~~~~^~~~~~~~~~~~~~~
split.cpp:280:13: warning: unused variable 'u' [-Wunused-variable]
  280 |     for(int u:E2[i]){
      |             ^
split.cpp:342:12: warning: unused variable 'i' [-Wunused-variable]
  342 |    for(int i:X){
      |            ^
#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...