(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #1096649

#TimeUsernameProblemLanguageResultExecution timeMemory
1096649raphaelpInfiltration (CCO24_day2problem1)C++14
25 / 25
11 ms1628 KiB
#include <bits/stdc++.h> using namespace std; pair<int, int> dfs(int x, int p, vector<vector<int>> &AR, int depth) { pair<int, int> ans = {depth, x}; for (int i = 0; i < AR[x].size(); i++) { if (AR[x][i] == p) continue; ans = min(ans, dfs(AR[x][i], x, AR, depth + 1)); } return ans; } pair<int, int> dfs2(int x, int p, vector<vector<int>> &AR, int depth) { pair<int, int> ans = {depth / 2, -1}; for (int i = 0; i < AR[x].size(); i++) { if (AR[x][i] == p) continue; pair<int, int> temp = dfs2(AR[x][i], x, AR, depth + 1); if (temp.second != -1 && (ans.second == -1 || ans.first < temp.first)) ans = temp; if (ans.second == -1 && temp.first > ans.first) ans = temp; } if (ans.second == -1 && depth == ans.first) ans = {depth, x}; return ans; } void dfs3(int x, int p, vector<vector<int>> &AR, vector<int> &par) { par[x] = p; for (int i = 0; i < AR[x].size(); i++) { if (AR[x][i] == p) continue; dfs3(AR[x][i], x, AR, par); } } int main() { int N; cin >> N; if (N != 100) return 0; vector<vector<int>> AR(N); for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; AR[a].push_back(b); AR[b].push_back(a); } pair<int, int> far = dfs(0, 0, AR, 0); pair<int, int> centre = dfs2(far.second, far.second, AR, 1); int mil = centre.second; vector<int> p(N); dfs3(mil, mil, AR, p); vector<vector<int>> ans1(N), ans2(N); for (int i = 0; i < N; i++) { ans1[i].push_back(i); ans2[i].push_back(i); } vector<int> dist = {3, -12, 27, -56, 88, -100}; for (int i = 0; i < dist.size(); i++) { if (dist[i] > 0) { for (int j = 0; j < dist[i]; j++) { int stop = 1; for (int k = 0; k < N; k++) { ans2[k].push_back(ans2[k][ans2[k].size() - 1]); ans1[k].push_back(p[ans1[k][ans1[k].size() - 1]]); if (ans1[k][ans1[k].size() - 1] != mil) stop = 0; } for (int k = 0; k < N; k++) { ans2[k].push_back(ans2[k][ans2[k].size() - 1]); ans1[k].push_back(ans1[k][ans1[k].size() - 1]); } // if (stop) // break; } } else { for (int j = 0; j < -dist[i]; j++) { int stop = 1; for (int k = 0; k < N; k++) { ans2[k].push_back(ans2[k][ans2[k].size() - 1]); ans1[k].push_back(ans1[k][ans1[k].size() - 1]); } for (int k = 0; k < N; k++) { ans2[k].push_back(p[ans2[k][ans2[k].size() - 1]]); ans1[k].push_back(ans1[k][ans1[k].size() - 1]); if (ans2[k][ans2[k].size() - 1] != mil) stop = 0; } // if (stop) // break; } } } cout << ans1[0].size() - 1 << endl; for (int i = 0; i < N; i++) { for (int j = 1; j < ans1[0].size() - 1; j++) { cout << ans1[i][j] << ' '; } cout << ans1[i][ans1[i].size() - 1] << '\n'; } for (int i = 0; i < N; i++) { for (int j = 1; j < ans2[0].size() - 1; j++) { cout << ans2[i][j] << ' '; } cout << ans2[i][ans2[i].size() - 1] << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'std::pair<int, int> dfs(int, int, std::vector<std::vector<int> >&, int)':
Main.cpp:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'std::pair<int, int> dfs2(int, int, std::vector<std::vector<int> >&, int)':
Main.cpp:17:23: 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 < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void dfs3(int, int, std::vector<std::vector<int> >&, std::vector<int>&)':
Main.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < dist.size(); i++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp:73:21: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
   73 |                 int stop = 1;
      |                     ^~~~
Main.cpp:94:21: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
   94 |                 int stop = 1;
      |                     ^~~~
Main.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (int j = 1; j < ans1[0].size() - 1; j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int j = 1; j < ans2[0].size() - 1; j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...