이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cassert>
using namespace std;
const int maxn=2e5+5;
int vel[3];
int ind[3];
vector < int > ms[maxn];
int n, m;
bool cmp(int a, int b){
return vel[a]<vel[b];
}
int djeca[maxn];
int parent[maxn];
int dfs(int x, int prosl){
djeca[x]=1;
parent[x]=prosl;
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]!=prosl){
djeca[x]+=dfs(ms[x][i], x);
}
}
return djeca[x];
}
int centroid(int x, int prosl){
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]!=prosl && djeca[ms[x][i]]>n/2){
return centroid(ms[x][i], x);
}
}
return x;
}
vector < int > col;
int treba;
int koja, zamj;
void dfs1(int x, int prosl){
if(treba){
treba--;
col[x]=koja;
}
else{
col[x]=zamj;
}
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]!=prosl){
dfs1(ms[x][i], x);
}
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n=N;
col.resize(n, 0);
m=p.size();
vel[0]=a;
vel[1]=b;
vel[2]=c;
for(int i=0; i<3; i++){
ind[i]=i;
}
sort(ind, ind+3, cmp);
for(int i=0; i<m; i++){
ms[p[i]].push_back(q[i]);
ms[q[i]].push_back(p[i]);
}
if(m!=n-1){
assert(0);
}
dfs(0, 0);
int x=centroid(0, 0);
dfs(x, x);
int traz=vel[ind[0]];
int pos, naj=1e9;
for(int i=0; i<n; i++){
if(djeca[i]>=traz){
if(naj>djeca[i]){
naj=djeca[i];
pos=i;
}
}
}
if(n-naj<vel[ind[1]]){
return col;
}
treba=traz;
koja=ind[0]+1;
zamj=ind[2]+1;
dfs1(pos, parent[pos]);
koja=ind[1]+1;
treba=vel[ind[1]];
dfs1(parent[pos], pos);
return col;
}
컴파일 시 표준 에러 (stderr) 메시지
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:104:6: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
104 | dfs1(parent[pos], pos);
| ~~~~^~~~~~~~~~~~~~~~~~
# | 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... |