Submission #291663

#TimeUsernameProblemLanguageResultExecution timeMemory
291663spdskatrVillage (BOI20_village)C++14
75 / 100
202 ms35436 KiB
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> using namespace std; int N, dp[100005][2], ans[100005], conn[100005], seen[100005]; // 0 = isolated, 1 = attached vector<int> graph[100005], g2[100005]; vector<int> broken[100005], unbroken[100005]; vector<int> order; int sz[100005], ans2[100005], tot; vector<int> nds; void dfs(int x, int p) { dp[x][1] = 0; int mindiff = 2069696969; for (int v : graph[x]) { if (v != p) { dfs(v, x); int df = max(0, dp[v][0] + 1 - dp[v][1]); if (mindiff > df) { mindiff = df; conn[x] = v; } if (dp[v][0] + 1 > dp[v][1]) { broken[x].push_back(v); dp[x][1] += dp[v][0] + 1; } else { unbroken[x].push_back(v); dp[x][1] += dp[v][1]; } } } dp[x][0] = dp[x][1] - mindiff; } void dfs2(int x, int state) { int keep = -1; if (state == 0) { keep = conn[x]; } if (keep != -1) { g2[x].push_back(keep); g2[keep].push_back(x); dfs2(keep, 1); } for (int v : broken[x]) { if (v != keep) { dfs2(v, 0); } } for (int v : unbroken[x]) { if (v != keep) { g2[x].push_back(v); g2[v].push_back(x); dfs2(v, 1); } } } void dfs3(int x, int p) { seen[x] = 1; order.push_back(x); for (int v : g2[x]) if (v != p) dfs3(v, x); } void dfs4(int x, int p) { sz[x] = 1; for (int v : graph[x]) if (v != p) { dfs4(v, x); tot += min(sz[v], N - sz[v]); sz[x] += sz[v]; } } void dfs5(int x, int p) { nds.push_back(x); for (int v : graph[x]) if (v != p) dfs5(v, x); } int main() { scanf("%d", &N); for (int i = 0; i < N-1; i++) { int a, b; scanf("%d %d", &a, &b); graph[a].push_back(b); graph[b].push_back(a); } dfs(1, 1); dfs2(1, 0); // Create g2 for (int i = 1; i <= N; i++) { if (!seen[i]) { order.clear(); dfs3(i, i); for (int j = 0; j < order.size(); j++) { ans[order[j]] = order[(j+1)%order.size()]; } } } // Find centroid dfs4(1, 1); int cent = 1, rip = 1; while (rip) { rip = 0; for (int v : graph[cent]) { if (sz[v] < sz[cent] && sz[v] > (sz[1] / 2)) { rip = 1; cent = v; break; } } } // Cent is centroid for (int v : graph[cent]) { dfs5(v, cent); } if (nds.size() & 1) { nds.push_back(cent); int of = nds.size() / 2; for (int i = 0; i + of < nds.size(); i++) { ans2[nds[i]] = nds[i + of]; ans2[nds[i+of]] = nds[i]; } } else { int of = nds.size() / 2; ans2[nds[0]] = cent; ans2[cent] = nds[of]; ans2[nds[of]] = nds[0]; for (int i = 1; i + of < nds.size(); i++) { ans2[nds[i]] = nds[i+of]; ans2[nds[i+of]] = nds[i]; } } printf("%d %d\n", 2 * (N-1-dp[1][0]), 2 * tot); for (int i = 1; i <= N; i++) { if (i == 1) printf("%d", ans[i]); else printf(" %d", ans[i]); } printf("\n"); for (int i = 1; i <= N; i++) { if (i == 1) printf("%d", ans2[i]); else printf(" %d", ans2[i]); } printf("\n"); }

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for (int j = 0; j < order.size(); j++) {
      |                    ~~^~~~~~~~~~~~~~
Village.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int i = 0; i + of < nds.size(); i++) {
      |                   ~~~~~~~^~~~~~~~~~~~
Village.cpp:131:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for (int i = 1; i + of < nds.size(); i++) {
      |                   ~~~~~~~^~~~~~~~~~~~
Village.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Village.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...