Submission #131549

#TimeUsernameProblemLanguageResultExecution timeMemory
131549SamAndMousetrap (CEOI17_mousetrap)C++17
20 / 100
2 ms376 KiB
#include <bits/stdc++.h> using namespace std; const int N = 12, INF = 1000000009; int n, t, m; vector<int> a[N]; bool c[N]; void dfs0(int x, int p) { if (x == t) { c[x] = true; return; } for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (h == p) continue; dfs0(h, x); if (c[h]) { c[x] = true; return; } } } void rec(int x, int p, int i, int q, int sq, vector<int> qq); int dp[N][N]; bool cc[N][N]; void dfs(int x, int q, int p) { if (cc[x][q]) return; cc[x][q] = true; if (x == t) { dp[x][q] = 0; return; } vector<int> v; rec(x, p, 0, q, q, v); } void rec(int x, int p, int i, int q, int sq, vector<int> qq) { if (i == a[x].size()) { vector<int> v; int vv = 0; for (int ii = 0; ii < a[x].size(); ++ii) { int h = a[x][ii]; if (h == p) continue; if (!c[h]) { dfs(h, qq[ii], x); v.push_back(dp[h][qq[ii]]); } else { dfs(h, qq[ii] + 1, x); vv = dp[h][qq[ii] + 1]; } } sort(v.begin(), v.end()); int yans = 0; for (int i = v.size() - q - 2; i >= 0; i -= 2) yans += v[i]; yans += v.size(); yans += vv; dp[x][sq] = min(dp[x][sq], yans); return; } if (a[x][i] == p) { qq.push_back(0); rec(x, p, i + 1, q, sq, qq); qq.pop_back(); return; } for (int j = 0; j <= q; ++j) { qq.push_back(j); rec(x, p, i + 1, q - j, sq, qq); qq.pop_back(); } } int main() { //freopen("input.txt", "r", stdin); scanf("%d%d%d", &n, &t, &m); for (int i = 0; i < n - 1; ++i) { int x, y; scanf("%d%d", &x, &y); a[x].push_back(y); a[y].push_back(x); } dfs0(m, m); for (int x = 1; x <= n; ++x) { for (int i = 0; i < N; ++i) { dp[x][i] = INF; } } dfs(m, 0, m); cout << dp[m][0] << endl; return 0; }

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs0(int, int)':
mousetrap.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'void rec(int, int, int, int, int, std::vector<int>)':
mousetrap.cpp:50:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i == a[x].size())
         ~~^~~~~~~~~~~~~~
mousetrap.cpp:54:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int ii = 0; ii < a[x].size(); ++ii)
                          ~~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &t, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...