Submission #103725

#TimeUsernameProblemLanguageResultExecution timeMemory
103725E869120Mousetrap (CEOI17_mousetrap)C++14
45 / 100
2615 ms245980 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #pragma warning (disable: 4996) const int MAX_N = (1 << 20); int N, A, B, E[MAX_N], F[MAX_N], dist[MAX_N], dp[MAX_N][22], val[MAX_N], pl[MAX_N]; bool used[MAX_N]; vector<int>X[MAX_N], Z[MAX_N], lis[MAX_N]; void dfs1(int pos, int dep) { used[pos] = true; dist[pos] = dep; for (int i = 0; i < X[pos].size(); i++) { if (used[X[pos][i]] == true) continue; dp[X[pos][i]][0] = pos; dfs1(X[pos][i], dep + 1); } } int prevs(int pos, int x) { for (int i = 21; i >= 0; i--) { if (x >= (1 << i)) { pos = dp[pos][i]; x -= (1 << i); } } return pos; } int lca(int u, int v) { if (dist[u] > dist[v]) swap(u, v); v = prevs(v, dist[v] - dist[u]); if (u == v) return u; for (int i = 21; i >= 0; i--) { if (dp[u][i] != dp[v][i]) { u = dp[u][i]; v = dp[v][i]; } } return dp[u][0]; } int ret[MAX_N], root = 0, G = 2; int dfs2(int pos) { used[pos] = true; int bonus = 0; if (pos == root) bonus = 1; if ((int)Z[pos].size() + bonus <= 1) { return 0; } if ((int)Z[pos].size() + bonus == 2) { return 1; } vector<int>vec; for (int i = 0; i < Z[pos].size(); i++) { if (used[Z[pos][i]] == true) continue; vec.push_back(dfs2(Z[pos][i])); } sort(vec.begin(), vec.end()); int GG = 2; if (pos == root) GG = G; int V = vec[max(0, (int)vec.size() - GG)]; if (vec.size() < GG) V = 0; return V + vec.size(); } int main() { scanf("%d%d%d", &N, &A, &B); for (int i = 1; i <= N - 1; i++) { scanf("%d%d", &E[i], &F[i]); X[E[i]].push_back(F[i]); X[F[i]].push_back(E[i]); } dfs1(B, 0); for (int i = 0; i < 21; i++) { for (int j = 1; j <= N; j++) dp[j][i + 1] = dp[dp[j][i]][i]; } for (int i = 1; i <= N; i++) { int v = lca(A, i); val[i] = dist[v]; if (v == i) pl[dist[v]] = i; else lis[dist[v]].push_back(i); } int FinalAns = 0; for (int i = 1; i <= N; i++) used[i] = false; for (int i = 0; i < dist[A]; i++) { for (int j = 0; j < lis[i].size(); j++) { int u = lis[i][j], v = dp[u][0]; Z[u].push_back(v); Z[v].push_back(u); } root = pl[i]; int rem = dfs2(pl[i]); if (rem >= 1) { G = 1000000; } else G++; FinalAns += rem; } cout << FinalAns << endl; return 0; }

Compilation message (stderr)

mousetrap.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
mousetrap.cpp: In function 'void dfs1(int, int)':
mousetrap.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int dfs2(int)':
mousetrap.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Z[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
mousetrap.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (vec.size() < GG) V = 0;
      ~~~~~~~~~~~^~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lis[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
mousetrap.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &E[i], &F[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...