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 <bits/stdc++.h>
//#include "split.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int ans, n, A, B, label[NMAX], cnt;
int dfsn[NMAX], low[NMAX], sz[NMAX], t;
vector<int> adj[NMAX];
void color(int x, int c){
if(label[x] != -1) return;
label[x] = (cnt-- > 0 ? c : 2);
for(int& nx : adj[x])
if(dfsn[nx] > dfsn[x]) color(nx, c);
return;
}
void dfs(int x, int p){
vector<int> C;
dfsn[x] = low[x] = ++t;
sz[x] = 1;
int mx = 0;
for(int& nx : adj[x])
if(nx != p) {
if(!dfsn[nx]){
dfs(nx, x);
low[x] = min(low[x], low[nx]);
sz[x] += sz[nx];
C.emplace_back(nx);
mx = max(mx, sz[nx]);
}
else low[x] = min(low[x], dfsn[nx]);
}
if(!ans && sz[x] >= A && mx < A){
int d = sz[x], u = n - d;
label[x] = 0;
cnt = A - 1;
for(int& nx : C){
if(d - sz[nx] >= A && low[nx] < dfsn[x]) u += sz[nx], d -= sz[nx];
else color(nx, 0);
}
ans = (u >= A ? 1 : -1);
}
return;
}
vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q) {
n = n_;
vector<pair<int, int>> arr = {{a, 1}, {b, 2}, {c, 3}};
sort(all(arr));
A = arr[0].first;
B = arr[1].first;
vector<int> res(n, 0);
for(int i = 0; i < p.size(); i++){
adj[p[i]].emplace_back(q[i]);
adj[q[i]].emplace_back(p[i]);
}
memset(label, -1, sizeof(label));
dfs(0, -1);
if(ans == -1) return res;
cnt = B;
color(0, 1);
for(int i = 0; i < n; i++) res[i] = arr[label[i]].second;
return res;
}
/*
int main(void){
int n, m, a, b, c;
cin >> n >> a >> b >> c;
cin >> m;
vector<int> p(m), q(m);
for(int i = 0; i < m; i++) cin >> p[i] >> q[i];
auto v = find_split(n, a, b, c, p, q);
for(int& x : v) cout << x << ' ';
return 0;
}
*/
Compilation message (stderr)
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | 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... |