Submission #1206313

#TimeUsernameProblemLanguageResultExecution timeMemory
1206313thelegendary08Split the Attractions (IOI19_split)C++17
33 / 100
570 ms1114112 KiB
#include "split.h" #include<bits/stdc++.h> #define f0r(i,n) for(int i = 0; i<n; i++) #define FOR(i, k, n) for(int i = k; i<n; i++) #define pb push_back #define vi vector<int> #define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n'; #define dout(x) cout<<x<<' '<<#x<<'\n'; #define pii pair<int,int> #define vpii vector<pii> #define vb vector<bool> #define mp make_pair using namespace std; const int mxn = 2e5 + 5; vector<vi> adj(mxn); int m; vi par(mxn); vi sts(mxn); int dfs(int node, int from){ int cur = 1; par[node] = from; for(auto u : adj[node]){ if(u == from)continue; cur += dfs(u,node); } sts[node] = cur; return cur; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { m = p.size(); vi deg(n); f0r(i,m){ int x = p[i]; int y = q[i]; adj[x].pb(y); adj[y].pb(x); deg[x]++; deg[y]++; } vi ans(n, 3); if(a == 1){ queue<int>q; q.push(0); int cnt = 0; vb vis(n); vis[0] = 1; while(!q.empty() && cnt < b){ int node = q.front(); q.pop(); cnt++; ans[node] = 2; for(auto u : adj[node]){ if(vis[u])continue; vis[u] = 1; q.push(u); } } f0r(i,n){ if(ans[i] == 3){ ans[i] = 1; break; } } } else{ //subtask 1 /* int st = -1; f0r(i, n){ if(deg[i] == 1)st = i; } if(st == -1)st = 0; queue<int>q; vb vis(n); vis[st] = 1; q.push(st); int cnt = 1; ans[st] = 1; while(!q.empty() && cnt < a){ int node = q.front(); q.pop(); for(auto u : adj[node]){ if(vis[u])continue; vis[u] = 1; cnt++; ans[u] = 1; q.push(u); break; } } cnt = 0; while(!q.empty() && cnt < b){ int node = q.front(); q.pop(); for(auto u : adj[node]){ if(vis[u])continue; vis[u] = 1; cnt++; ans[u] = 2; q.push(u); } } */ f0r(i, n)ans[i] = -1; vpii thing; thing.pb(mp(a,1)); thing.pb(mp(b,2)); thing.pb(mp(c,3)); sort(thing.begin(), thing.end()); dfs(0, -1); bool ok = 0; FOR(i, 1, n){ int x = sts[i]; int y = n - sts[i]; if(thing[0].first <= x && thing[1].first <= y){ // dout(i); queue<int>q; q.push(i); int cnt = 0; vb vis(n); vis[i] = 1; while(!q.empty() && cnt < thing[0].first){ int node = q.front(); q.pop(); cnt++; ans[node] = thing[0].second; for(auto u : adj[node]){ if(vis[u])continue; if(u == par[node])continue; vis[u] = 1; q.push(u); } } q = queue<int>(); q.push(par[i]); cnt = 0; vis[par[i]] = 1; while(!q.empty() && cnt < thing[1].first){ int node = q.front(); q.pop(); cnt++; ans[node] = thing[1].second; for(auto u : adj[node]){ if(vis[u])continue; vis[u] = 1; q.push(u); } } ok = 1; } else if(thing[1].first <= x && thing[0].first <= y){ // cout<<i<<'\n'; // cout<<x<<' '<<y<<'\n'; queue<int>q; q.push(i); int cnt = 0; vb vis(n); vis[i] = 1; while(!q.empty() && cnt < thing[1].first){ int node = q.front(); q.pop(); cnt++; ans[node] = thing[1].second; for(auto u : adj[node]){ if(vis[u])continue; if(u == par[node])continue; vis[u] = 1; q.push(u); } } // vout(ans); q = queue<int>(); q.push(par[i]); cnt = 0; vis[par[i]] = 1; while(!q.empty() && cnt < thing[0].first){ int node = q.front(); q.pop(); // dout(node); cnt++; ans[node] = thing[0].second; for(auto u : adj[node]){ if(vis[u])continue; vis[u] = 1; q.push(u); } } ok = 1; } if(ok)break; } if(!ok){ f0r(i,n)ans[i] = 0; } else{ f0r(i,n)if(ans[i] == -1)ans[i] = thing[2].second; } } return ans; }
#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...