Submission #189319

#TimeUsernameProblemLanguageResultExecution timeMemory
189319kig9981Split the Attractions (IOI19_split)C++17
0 / 100
197 ms20508 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; vector<int> adj[100000], tree[100000], ans; int node_cnt, num[100000], low[100000], cnt[100000], parent[100000], G[100000]; void dfs(int c) { num[c]=low[c]=++node_cnt; cnt[c]=1; for(auto n: adj[c]) { if(num[n]==0) { parent[n]=c; tree[n].push_back(c); tree[c].push_back(n); dfs(n); low[c]=min(low[c],low[n]); cnt[c]+=cnt[n]; } else if(c!=parent[n]) low[c]=min(low[c],num[n]); } } int centroid(int c) { for(auto n: tree[c]) if(parent[n]==c && 2*cnt[n]>cnt[0]) return centroid(n); return c; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { vector<pair<int,int>> V; queue<int> Q; int tot=0; ans.clear(); for(int i=node_cnt=0;i<n;i++) { num[i]=0; G[i]=-1; adj[i].clear(); tree[i].clear(); } V.emplace_back(a,1); V.emplace_back(b,2); V.emplace_back(c,3); sort(V.begin(),V.end()); for(int i=0;i<p.size();i++) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } dfs(0); c=centroid(0); ans.resize(n); for(auto n: tree[c]) { if(parent[n]==c && cnt[n]>=V[1].first || parent[c]==n && cnt[0]-cnt[c]>=V[1].first) { ans[n]=V[1].second; ans[c]=V[0].second; Q.push(n); V[1].first--; V[0].first--; while(!Q.empty() && V[1].first) { int c=Q.front(); Q.pop(); for(auto n: tree[c]) if(ans[n]==0 && V[1].first) { ans[n]=ans[c]; V[1].first--; Q.push(n); } } Q.push(c); while(!Q.empty() && V[0].first) { int c=Q.front(); Q.pop(); for(auto n: adj[c]) if(ans[n]==0 && V[0].first) { ans[n]=ans[c]; V[0].first--; Q.push(n); } } for(auto &v: ans) if(v==0) v=V[2].second; return ans; } else if(parent[n]==c && cnt[n]>=V[0].first || parent[c]==n && cnt[0]-cnt[c]>=V[0].first) { ans[n]=V[0].second; ans[c]=V[1].second; V[1].first--; V[0].first--; Q.push(n); while(!Q.empty() && V[0].first) { int c=Q.front(); Q.pop(); for(auto n: tree[c]) if(ans[n]==0 && V[0].first) { ans[n]=ans[c]; V[0].first--; Q.push(n); } } Q.push(c); while(!Q.empty() && V[1].first) { int c=Q.front(); Q.pop(); for(auto n: adj[c]) if(ans[n]==0 && V[1].first) { ans[n]=ans[c]; V[1].first--; Q.push(n); } } for(auto &v: ans) if(v==0) v=V[2].second; return ans; } } G[c]=0; G[parent[c]]=1; Q.push(parent[c]); while(!Q.empty()) { int c=Q.front(); Q.pop(); for(auto n: tree[c]) if(G[n]==-1) { G[n]=G[c]; Q.push(n); } } tot=n-cnt[c]; for(auto n: tree[c]) if(parent[n]==c && low[n]<num[c]) { G[n]=1; Q.push(n); while(!Q.empty()) { int c=Q.front(); Q.pop(); for(auto n: tree[c]) if(G[n]==-1) { G[n]=G[c]; Q.push(n); } } if((tot+=cnt[n])>=V[0].first) { ans[parent[c]]=V[0].second; ans[c]=V[1].second; V[1].first--; V[0].first--; Q.push(parent[c]); while(!Q.empty() && V[0].first) { int c=Q.front(); Q.pop(); for(auto n: adj[c]) if(G[n]==G[c] && ans[n]==0 && V[0].first) { ans[n]=ans[c]; V[0].first--; Q.push(n); } } Q.push(c); while(!Q.empty() && V[1].first) { int c=Q.front(); Q.pop(); for(auto n: adj[c]) if(ans[n]==0 && V[1].first) { ans[n]=ans[c]; V[1].first--; Q.push(n); } } for(auto &v: ans) if(v==0) v=V[2].second; return ans; } } return ans; }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++) {
              ~^~~~~~~~~
split.cpp:55:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(parent[n]==c && cnt[n]>=V[1].first || parent[c]==n && cnt[0]-cnt[c]>=V[1].first) {
      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
split.cpp:83:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   else if(parent[n]==c && cnt[n]>=V[0].first || parent[c]==n && cnt[0]-cnt[c]>=V[0].first) {
           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...