이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int maxx = 200000;
int N , pos = -1 , par , cent;
int dp[maxx];
vector< pair<int,int> >spl;
vector<int>adj[maxx];
void dfs(int s,int p) {
dp[s] = 1;
bool f = true;
for (int to : adj[s]) {
if (to == p)continue;
dfs(to , s);
if (dp[to] >= spl[0].F) {
if (pos == -1)pos = to , par = s;
else if (dp[pos] > dp[to])pos = to , par = s;
}
f &= (dp[to] <= N / 2);
dp[s] += dp[to];
}
f &= (N - dp[s] <= N / 2);
if (f)cent = s;
}
vector<int>res;
int cnt = 0;
void label(int s,int p,int need,int mark) {
cnt++;
res[s] = mark;
if (cnt == need)return;
for (int to : adj[s]) {
if (to == p)continue;
label(to , s , need , mark);
if (cnt == need)return;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n;
res.resize(n , 0);
spl.push_back({a , 1});
spl.push_back({b , 2});
spl.push_back({c , 3});
sort(spl.begin(),spl.end());
int m = p.size();
if (n != m + 1)return res;
for (int i = 0;i<m;i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs(1 , -1);
int rt = cent;
dfs(rt , -1);
if (pos == -1)return res;
if (n - dp[pos] < spl[1].F)return res;
label(pos , par , spl[0].F , spl[0].S);
cnt = 0;
label(rt , -1 , spl[1].F , spl[0].S);
for (int i = 0;i<n;i++)
if (res[i] == 0)res[i] = spl[2].S;
return res;
}
# | 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... |