제출 #1055656

#제출 시각아이디문제언어결과실행 시간메모리
1055656HD1Split the Attractions (IOI19_split)C++14
0 / 100
471 ms1048576 KiB
#include "split.h" #include <bits/stdc++.h> #define all(s) s.begin(),s.end() #define sz(s) int(s.size()) #define pb push_back #define pb push_back #define ff first #define ss second typedef long long ll; //typedef pair<int,int> ii; const ll MAX=1e6+10; using namespace std; vector<int> gfo[MAX]; vector<pair<ll,ll>> ord; ll tam[MAX], m[MAX]; ll a, b, c, n; bool xd=false; void dfstams(ll u, ll f){ for(auto v:gfo[u]){ if(v!=f){ dfstams(v,u); tam[u]+=tam[v]; } } tam[u]++; return; } ll cont; void dfs(ll u, ll f, ll marc){ if(cont==ord[marc].ff)return; m[u]=ord[marc].ss; cont++; if(cont==ord[marc].ff)return; for(auto v:gfo[u]){ if(v!=f){ dfs(v,u,marc); } } return; } bool lock(ll u, ll v){//arista if(tam[u]>tam[v])swap(u,v); ll q=n-tam[u]; ll p=tam[u]; cont=0; if(p>=ord[0].ff && q>=ord[1].ff){ dfs(u, v, 0); cont=0; dfs(v, u, 1); xd=true; return true; } return false; } void clean(){ xd=false; ord.clear(); for(int i=0; i<n; i++){ gfo[i].clear(); tam[i]=0; m[i]=0; } return; } vector<int> find_split(int N, int A, int B, int C, vector<int> u, vector<int> v) { a=A; b=B; c=C; n=N; ord.pb({a,1}); ord.pb({b,2}); ord.pb({c,3}); sort(all(ord)); vector<int> res; for(int i=0; i<sz(u); i++){ gfo[u[i]].pb(v[i]); gfo[v[i]].pb(u[i]); } dfstams(0, 0); for(ll i=0; i<n; i++){ for(ll v:gfo[i]){ if(lock(i,v))break; } if(xd)break; } for(int i=0; i<n; i++){ if(xd && m[i]==0){ m[i]=ord[2].ss; } } for(int i=0; i<n; i++){ res.pb(m[i]); } clean(); return res; } /* 9 8 2 3 4 0 1 0 7 0 2 1 6 1 3 2 5 2 8 2 4 8 7 2 3 3 0 1 1 2 1 7 1 3 3 4 4 5 4 6 7 6 4 2 2 */
#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...