제출 #836520

#제출 시각아이디문제언어결과실행 시간메모리
836520AntekbSplit the Attractions (IOI19_split)C++17
0 / 100
2073 ms32696 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]; 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]]){ 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]){ 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]; pre[v]=1; for(int u:E2[v]){ if(!pre[u]){ dfs_sz(u); siz[v]+=siz[u]; } } } vi find(int a, vi dozw){ 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); } } } assert(V.size()>=a); V.resize(a); return V; } 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); 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); } } dfs_cent(0); 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:E2[cent]){ if(siz[u]>=A){ deb(u, siz[u], A); vi V; V.pb(u); for(int i=0; i<V.size(); i++){ int v=V[i]; for(int uu:E2[v]){ if(siz[uu]<siz[v]){ V.pb(uu); } } } for(int i=0; i<V.size(); i++){ int v=V[i]; for(int uu:kto[v]){ deb(uu); if(uu!=v){ V.pb(uu); } } } vi dozw(n); for(int i:V){ dozw[i]=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); } bb=1; break; } } if(!bb){ return res; } 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:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
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:106:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |  assert(V.size()>=a);
      |         ~~~~~~~~^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(int i=0; i<uu.size(); i++){
      |               ~^~~~~~~~~~
split.cpp:153:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |    for(int i=0; i<V.size(); i++){
      |                 ~^~~~~~~~~
split.cpp:161:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |    for(int i=0; i<V.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...