제출 #418828

#제출 시각아이디문제언어결과실행 시간메모리
418828ly20Village (BOI20_village)C++17
100 / 100
132 ms20492 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...