Submission #1060748

#TimeUsernameProblemLanguageResultExecution timeMemory
1060748MilosMilutinovicThe Ties That Guide Us (CEOI23_incursion)C++17
100 / 100
281 ms16096 KiB
#include "incursion.h" #include <bits/stdc++.h> using namespace std; vector<int> mark(vector<pair<int, int>> e, int safe) { --safe; int n = (int) e.size() + 1; vector<vector<int>> g(n); for (int i = 0; i + 1 < n; i++) { --e[i].first; --e[i].second; g[e[i].first].push_back(e[i].second); g[e[i].second].push_back(e[i].first); } int root; { vector<int> sz(n); function<void(int, int)> Dfs = [&](int v, int pv) { sz[v] = 1; for (int u : g[v]) { if (u == pv) { continue; } Dfs(u, v); sz[v] += sz[u]; } }; Dfs(0, 0); vector<int> cen; function<int(int, int)> FindCentroid = [&](int v, int pv) { if (sz[v] * 2 == n) { cen.push_back(pv); } for (int u : g[v]) { if (u == pv || sz[u] * 2 < n) { continue; } return FindCentroid(u, v); } cen.push_back(v); return v; }; root = FindCentroid(0, 0); if ((int) cen.size() == 2) { vector<int> que(1, safe); vector<bool> was(n); was[safe] = true; for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; if (i == cen[0] || i == cen[1]) { root = i; break; } for (int j : g[i]) { if (!was[j]) { que.push_back(j); was[j] = true; } } } } } int cnt = 0; for (int i = 0; i < n; i++) { if ((int) g[i].size() == 2) { cnt += 1; } } /* if (cnt == 1) { for (int i = 0; i < n; i++) { if ((int) g[i].size() == 2) { root = i; } } } */ vector<int> dfn(n); vector<int> dfo(n); int T = -1; function<void(int, int)> Dfs = [&](int v, int pv) { dfn[v] = ++T; for (int u : g[v]) { if (u == pv) { continue; } Dfs(u, v); } dfo[v] = T; }; Dfs(root, root); vector<int> seq(n); for (int i = 0; i < n; i++) { if (dfn[i] <= dfn[safe] && dfo[safe] <= dfo[i]) { seq[i] = 1; } else { seq[i] = 0; } } return seq; } void locate(vector<pair<int, int>> e, int curr, int t) { --curr; int n = (int) e.size() + 1; vector<vector<int>> g(n); for (int i = 0; i + 1 < n; i++) { --e[i].first; --e[i].second; g[e[i].first].push_back(e[i].second); g[e[i].second].push_back(e[i].first); } vector<int> cen; { vector<int> sz(n); function<void(int, int)> Dfs = [&](int v, int pv) { sz[v] = 1; for (int u : g[v]) { if (u == pv) { continue; } Dfs(u, v); sz[v] += sz[u]; } }; Dfs(0, 0); function<void(int, int)> Find = [&](int v, int pv) { if (sz[v] * 2 == n) { cen.push_back(pv); } for (int u : g[v]) { if (u == pv || sz[u] * 2 < n) { continue; } Find(u, v); return; } cen.push_back(v); }; Find(0, 0); } int root = cen[0]; int cnt = 0; for (int i = 0; i < n; i++) { if ((int) g[i].size() == 2) { cnt += 1; } } /* if (cnt == 1) { for (int i = 0; i < n; i++) { if ((int) g[i].size() == 2) { root = i; } } } */ vector<int> x(n, -1); vector<int> pr(n); vector<int> sz(n); function<void(int, int)> Dfs = [&](int v, int pv) { pr[v] = pv; sz[v] = 1; for (int u : g[v]) { if (u == pv) { continue; } Dfs(u, v); sz[v] += sz[u]; if (x[v] == -1 || sz[x[v]] < sz[u]) { x[v] = u; } } }; Dfs(root, root); vector<bool> was(n); while (true) { was[curr] = true; if (curr == root && t == 0) { root = cen[1]; x = vector<int>(n, -1); Dfs(root, root); t = visit(root + 1); curr = root; continue; } if (t == 0) { t = visit(pr[curr] + 1); curr = pr[curr]; continue; } if (x[curr] == -1) { return; } int k = visit(x[curr] + 1); if (k == 1) { curr = x[curr]; t = k; continue; } was[x[curr]] = true; visit(curr + 1); bool found = false; for (int u : g[curr]) { if (u == pr[curr] || u == x[curr] || was[u]) { continue; } int k = visit(u + 1); if (k == 1) { t = k; curr = u; found = true; break; } was[u] = true; visit(curr + 1); } if (!found) { return; } } }

Compilation message (stderr)

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...