제출 #809173

#제출 시각아이디문제언어결과실행 시간메모리
809173Username4132Split the Attractions (IOI19_split)C++14
100 / 100
134 ms33896 KiB
#include "split.h" #include<iostream> #include<vector> #include<algorithm> #include<cassert> using namespace std; using ll = long long; using pii = pair<int, int>; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define dforn(i, n) for(int i=n-1; i>=0; --i) #define PB push_back #define F first #define S second const int MAXN = 100010; int n, top, sito, A, B, C, tm, tin[MAXN], low[MAXN], si[MAXN]; bool vis[MAXN], done; vector<int> g[MAXN], tr[MAXN], ch; int target, obt=1, roo2; int ta2, ob2; vector<int> res[3]; bool marked[MAXN], used[MAXN]; void dfs1(int v, int p){ si[v]=1; vis[v]=true; tin[v]=low[v]=tm++; int forced=1; bool atm=true; vector<int> fset, rest; for(int to:g[v]){ if(to==p) continue; if(vis[to]){ low[v]=min(low[v], tin[to]); } else{ tr[v].PB(to); dfs1(to, v); si[v]+=si[to]; atm&=(si[to]<A); low[v]=min(low[v], low[to]); if(low[to]>=tin[v]){ forced+=si[to]; fset.PB(to); } else rest.PB(to); } } if(atm && (si[v]>=A) && !done){ done = true; roo2=p; if(forced>n-A) top=-1; else{ //assert(v!=0); top=v; sito=forced; for(int el:fset) ch.PB(el); while(sito<A){ ch.PB(rest.back()); sito+=si[rest.back()]; rest.pop_back(); } } } } void dfs2(int v){ if(obt<target){ used[v]=marked[v]=true; res[0].PB(v); ++obt; } for(int to:tr[v]) dfs2(to); } void dfs3(int v){ vis[v]=true; if(ob2<ta2){ ++ob2; used[v]=true; res[1].PB(v); } for(int to:g[v]) if(!vis[to] && !marked[to]) dfs3(to); } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) { n=N; vector<pii> col = {{a, 0}, {b, 1}, {c, 2}}; sort(col.begin(), col.end()); A = col[0].F, B = col[1].F, C = col[2].F; forn(i, p.size()){ g[p[i]].PB(q[i]); g[q[i]].PB(p[i]); } dfs1(0, 0); if(top==-1){ vector<int> ret(n, 0); return ret; } if(sito>=B) target=B, ta2=A; else target=A, ta2=B; marked[top]=used[top]=true; res[0].PB(top); for(int el:ch) dfs2(el); //assert((int)res[0].size() == target); forn(i, n) vis[i]=false; dfs3(roo2); assert(res[1].size()==ta2); if((int)res[0].size()==B) swap(res[0], res[1]); forn(i, n) if(!used[i]) res[2].PB(i); vector<int> ret(n); forn(i, 3) for(int el:res[i]) ret[el]=col[i].S + 1; return ret; }

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

In file included from /usr/include/c++/10/cassert:44,
                 from split.cpp:5:
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:115:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |  assert(res[1].size()==ta2);
      |         ~~~~~~~~~~~~~^~~~~
#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...