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 all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
using namespace std;
vector<pii> col;
vector<int> ans;
int sz[100009];
vector<int> g[100009];
void calcsz(int v, int prt){
sz[v] = 1;
for(auto u : g[v])
if(u != prt){
calcsz(u, v);
sz[v] += sz[u];
}
}
int lft, use;
void paint(int v, int prt){
if(lft <= 0) return;
ans[v] = use;
--lft;
for(auto u : g[v])
if(u != prt){
paint(u, v);
}
}
int ok = 0;
int N;
void dfs(int v, int prt){
if(ok) return;
for(auto u : g[v]){
if(sz[u] >= col[0].ff && N-sz[u] >= col[1].ff){
ok = 1;
lft = col[0].ff;
use = col[0].ss;
paint(u, v);
lft = col[1].ff;
use = col[1].ss;
paint(v, u);
return;
}
swap(col[0], col[1]);
if(sz[u] >= col[0].ff && N-sz[u] >= col[1].ff){
ok = 1;
lft = col[0].ff;
use = col[0].ss;
paint(u, v);
lft = col[1].ff;
use = col[1].ss;
paint(v, u);
return;
}
}
for(auto u : g[v]){
if(u == prt) continue;
int vbef = sz[v];
int ubef = sz[u];
sz[v] -= sz[u];
sz[u] += sz[v];
dfs(u, v);
sz[v] = vbef;
sz[u] = ubef;
}
}
void dfssp(int v){
if(lft <= 0) return;
--lft;
ans[v] = use;
for(auto u : g[v])
if(ans[u] == 0)
dfssp(u);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n;
ans.resize(n);
if(a == 1 || p.size() != n-1){
lft = b; use = 2;
dfssp(0);
for(int i = 0; i < n; ++i)
if(ans[i] == 0){
lft = a;
use = 1;
dfssp(i);
break;
}
for(int i = 0; i < n; ++i)
if(ans[i] == 0){
ans[i] = 3;
}
return ans;
}
col = {{a, 1}, {b, 2}, {c, 3}};
sort(all(col));
for(int i = 0; i < p.size(); ++i){
g[p[i]].pb(q[i]);
g[q[i]].pb(p[i]);
}
calcsz(0, -1);
dfs(0, -1);
if(ok == 0) return ans;
for(auto &u : ans)
if(u == 0)
u = col[2].ss;
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:88:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
88 | if(a == 1 || p.size() != n-1){
| ~~~~~~~~~^~~~~~
split.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | 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... |