이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
vector <int> grafo[MAXN];
long long mn, mx;
int rmn[MAXN], rmx[MAXN];
int cur[MAXN];
int grau[MAXN];
int marc[MAXN];
int dist[MAXN];
int sub[MAXN];
int n;
vector <int> cmp[MAXN];
int cm;
void dfs(int v, int p) {
sub[v] = 1;
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i];
if(viz == p) continue;
dfs(viz, v);
sub[v] += sub[viz];
}
mx += min(sub[v], n - sub[v]);
//printf("%d\n", sub[v]);
}
int dfs2(int v, int p) {
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i];
if(viz == p) continue;
if(sub[viz] > n / 2) return dfs2(viz, v);
}
return v;
}
void dfs3(int v, int p) {
cmp[cm].push_back(v);
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i];
if(viz == p) continue;
dfs3(viz, v);
}
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n - 1; i++) {
int a, b;
scanf("%d %d", &a, &b);
grafo[a].push_back(b);
grafo[b].push_back(a);
grau[a]++; grau[b]++;
}
queue <int> fila;
for(int i = 1; i <= n; i++) {
rmn[i] = i; rmx[i] = i;
if(grau[i] == 1) fila.push(i);
}
while(!fila.empty()) {
int cur = fila.front(); fila.pop();
marc[cur] = 1;
int p = grafo[cur][0];
for(int i = 0 ;i < grafo[cur].size(); i++) {
int viz = grafo[cur][i];
grau[viz]--;
if(grau[viz] == 1) fila.push(viz);
if(marc[viz] == 0) p = viz;
}
if(rmn[cur] == cur) {
swap(rmn[cur], rmn[p]);
mn += 2;
}
}
dfs(1, 1);
int cn = dfs2(1, 1);
for(int i = 0; i < grafo[cn].size(); i++) {
dfs3(grafo[cn][i], cn);
cm++;
}
int mt = 1123456789;
int id = 0;
for(int i = 0; i < cm; i++) {
if(cmp[i].size() < mt) {
mt = cmp[i].size();
id = i;
}
}
if(n % 2 == 0) cmp[id].push_back(cn);
vector <int> temp;
for(int i = 0; i < cm; i++) {
for(int j = 0; j < cmp[i].size(); j++) temp.push_back(cmp[i][j]);
}
for(int i = 0; i < temp.size() / 2; i++) {
int pr = i + temp.size() / 2;
swap(rmx[temp[i]], rmx[temp[pr]]);
}
if(n % 2 == 1) swap(rmx[temp[0]], rmx[cn]);
printf("%lld %lld\n", mn, mx * 2);
for(int i = 1; i <= n; i++) {
printf("%d ", rmn[i]);
}
printf("\n");
for(int i = 1; i <= n; i++) {
printf("%d ", rmx[i]);
}
printf("\n");
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Village.cpp: In function 'void dfs(int, int)':
Village.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i = 0; i < grafo[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
Village.cpp: In function 'int dfs2(int, int)':
Village.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i = 0; i < grafo[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
Village.cpp: In function 'void dfs3(int, int)':
Village.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i = 0; i < grafo[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0 ;i < grafo[cur].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
Village.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 0; i < grafo[cn].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
Village.cpp:80:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if(cmp[i].size() < mt) {
| ~~~~~~~~~~~~~~^~~~
Village.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int j = 0; j < cmp[i].size(); j++) temp.push_back(cmp[i][j]);
| ~~^~~~~~~~~~~~~~~
Village.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i < temp.size() / 2; i++) {
| ~~^~~~~~~~~~~~~~~~~
Village.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Village.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |