This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |