Submission #824535

#TimeUsernameProblemLanguageResultExecution timeMemory
824535tomrukSplit the Attractions (IOI19_split)C++17
0 / 100
74 ms15092 KiB
#include "split.h" #include <bits/stdc++.h> #define N 100005 using namespace std; int par[N]; int sz[N]; vector<int> adj[N]; vector<int> adj2[N]; int sub[N]; int n; int find(int a){ if(a == par[a]) return a; return par[a] = find(par[a]); } bool merge(int a,int b){ a = find(a); b = find(b); if(a == b) return 0; par[a] = b; sz[b] += sz[a]; return 1; } int dfs1(int v,int pr){ sub[v] = 1; int ret = v; for(auto u:adj[v]){ if(u == pr)continue; int tmp = dfs1(u,v); sub[v] += sub[u]; if(sub[u] > n/2){ ret = tmp; } } return ret; } vector<int> res; int need; int ban = -1; bool ok[N]; void dfs2(int v,int pr,int col){ if(!need) return; res[v] = col; need--; for(auto u:adj[v]){ if(u == pr || ok[u])continue; dfs2(u,v,col); } } void dfs3(int v,int pr){ for(auto u:adj[v]){ if(u == pr)continue; merge(u,v); dfs3(u,v); } } bool vis[N]; void dfs4(int v,int col){ vis[v] = 1; if(!need) return; res[v] = col; need--; for(auto u:adj2[v]){ if(!ok[u] || vis[u])continue; dfs2(u,v,col); } } vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q){ n = _n; res.assign(n,0); for(int i = 0;i<n;i++){ par[i] = i; } for(int i = 0;i<p.size();i++){ if(merge(p[i],q[i])){ adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } adj2[p[i]].push_back(q[i]); adj2[q[i]].push_back(p[i]); } int cent = dfs1(0,-1); dfs1(cent,-1); vector<int> v = {a,b,c}; vector<int> ord = {0,1,2}; sort(ord.begin(),ord.end(),[&](int a,int b){ return v[a] < v[b]; }); for(int i = 0;i<n;i++){ par[i] = i; sz[i] = 1; } for(auto u:adj[cent]){ dfs3(u,cent); } for(int i = 0;i<p.size();i++){ if(p[i] == cent || q[i] == cent)continue; merge(p[i],q[i]); if(sz[find(p[i])] >= v[ord[1]]){ for(int j = 0;j<n;j++){ if(find(j) == find(p[i])){ ok[j] = 1; } } res.assign(n,1 + ord[2]); need = v[ord[1]]; dfs4(p[i],1 + ord[1]); need = v[ord[0]]; dfs2(cent,-1,1 + ord[0]); break; } if(sz[find(p[i])] >= v[ord[0]]){ for(int j = 0;j<n;j++){ if(find(j) == find(p[i])){ ok[j] = 1; } } res.assign(n,1 + ord[2]); need = v[ord[0]]; dfs4(p[i],1 + ord[0]); need = v[ord[1]]; dfs2(cent,-1,1 + ord[1]); break; } } return res; }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:77:17: 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<p.size();i++){
      |                ~^~~~~~~~~
split.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i = 0;i<p.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...