제출 #295013

#제출 시각아이디문제언어결과실행 시간메모리
295013FashoSplit the Attractions (IOI19_split)C++14
40 / 100
160 ms29048 KiB
#include <algorithm> #include <iostream> #include <cassert> #include <climits> #include <cstdlib> #include <cstring> #include <iomanip> #include <numeric> #include <cstdio> #include <string> #include <vector> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <map> #include <set> using namespace std; #define N 500005 #define ll long long int #define fo(i,x,y) for(int i=x;i<=y;i++) #define fs(ar,n) fo(i,1,n) cin>>ar[i] #define sp " " #define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false) #define pb push_back #define ppb pop_back #define fi first #define se second #define ii pair<int,int> #define lli pair<ll,ll> #define fast2 freopen ("in.txt","r",stdin);freopen ("out.txt","w",stdout); #define inf 1000000000 #define MP make_pair using namespace std; #include "split.h" using namespace std; lli pp[N]; ll nn,mm,x,y,z,flag,mark[N],tut[N],tt[N]; vector<int> v[N],ans(nn); ll f1(int ind,int back) { if(mark[ind]) return 0; tt[ind]=back; mark[ind]++; ll top=1; for(int i=0;i<v[ind].size();i++) { ll xx=v[ind][i]; if(mark[xx]) continue; top+=f1(xx,ind); } return tut[ind]=top; } void f(int ind,int back) { // cerr<<ind<<endl; if(mark[ind]) return; mark[ind]++; if(flag && !z) return; if(!flag && !y) return; if(!flag && y) ans[ind]=2,y--; if(flag && z) ans[ind]=3,z--; for(int i=0;i<v[ind].size();i++) { int xx=v[ind][i]; if(xx!=back) f(xx,ind); } } void f2(int ind,int back) { if(mark[ind] || !pp[1].fi) return; mark[ind]=1; pp[1].fi--; ans[ind]=pp[1].se; for(int i=0;i<v[ind].size();i++) { ll xx=v[ind][i]; if(mark[xx] || back==xx) continue; f2(xx,ind); } } void f3(int ind,int back) { if(mark[ind] || !pp[2].fi) return; mark[ind]=1; pp[2].fi--; ans[ind]=pp[2].se; for(int i=0;i<v[ind].size();i++) { ll xx=v[ind][i]; if(mark[xx] || back==xx) continue; f3(xx,ind); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { mm=p.size(); nn=n; x=a; y=b; z=c; int rt=0; fo(i,0,mm-1) { int at=p[i]; int bt=q[i]; v[at].pb(bt); v[bt].pb(at); } pp[1]=MP(a,1); pp[2]=MP(b,2); pp[3]=MP(c,3); sort(pp+1,pp+4); if(b>c) flag=1; // cerr<<ans.size()<<endl; ans.resize(nn); fo(i,0,nn-1) if(v[i].size()<2) rt=i; f1(rt,rt); memset(mark,0,sizeof(mark)); for(int i=0;i<n;i++) { // cout<<i<<sp<<tut[i]<<sp<<tt[i]<<endl; if(tut[i]>=pp[1].fi && n-tut[i]>=pp[2].fi) { f2(i,tt[i]); f3(tt[i],i); for(int j=0;j<n;j++) if(ans[j]==0) { int xxx=pp[3].se; ans[j]=xxx; } // cerr<<" HELLO"<<sp<<i<<endl; break; } else if(tut[i]>=pp[2].fi && n-tut[i]>=pp[1].fi) { f3(i,tt[i]); f2(tt[i],i); for(int j=0;j<n;j++) if(ans[j]==0) { int xxx=pp[3].se; ans[j]=xxx; } // cerr<<" HELLO"<<sp<<i<<endl; break; } } return ans; } // int main() { // fast2; // int n, m, a, b, c; // assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c)); // vector<int> p(m), q(m); // for (int i=0; i<m; i++) // assert(2 == scanf("%d%d", &p[i], &q[i])); // fclose(stdin); // vector<int> result = find_split(n, a, b, c, p, q); // for (int i=0; i<(int)result.size(); i++) // printf("%s%d", ((i>0)?" ":""), result[i]); // printf("\n"); // fclose(stdout); // return 0; // }

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

split.cpp: In function 'long long int f1(int, int)':
split.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
split.cpp: In function 'void f(int, int)':
split.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
split.cpp: In function 'void f2(int, int)':
split.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
split.cpp: In function 'void f3(int, int)':
split.cpp:107:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for(int i=0;i<v[ind].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...