# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
83808 | 2018-11-10T20:13:08 Z | updown1 | Mousetrap (CEOI17_mousetrap) | C++17 | 1477 ms | 145796 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define For(i, a, b) for(int i=a; i<b; i++) #define ffi For(i, 0, N) #define ffj For(j, 0, M) #define ffa ffi ffj #define s <<" "<< #define c <<" : "<< #define w cout #define e endl//"\n" #define pb push_back #define mp make_pair #define a first #define b second #define int ll //500,000,000 operations const int MAXN = 1000000; //Global Variables int N, T, M, moves[MAXN], toT[MAXN]; bool vis[MAXN]; vector<int> adj[MAXN], inp[MAXN]; void go(int at) { if (at == T) toT[at] = T; vis[at] = true; for (int i: inp[at]) if (!vis[i]) { adj[at].pb(i); go(i); if (toT[i] != -1) toT[at] = i; } } void go2 (int at, int curr) { //w<< at+1 s curr<<e; if (at == T || adj[at].empty()) return; vector<int> tim; for (int i: adj[at]) if (toT[at] != i) { go2(i, 0); tim.pb(moves[i]); } sort(tim.begin(), tim.end()); reverse(tim.begin(), tim.end()); if (toT[at] == -1) { For (i, 0, tim.size()) { if (i%2 == 0) moves[at]++; else moves[at] += 1 + tim[i]; } return; } //w<< "HERE" s at+1<<e; reverse(tim.begin(), tim.end()); while (curr > 0 && tim.size()) {curr--; moves[at]++; tim.pop_back();} reverse(tim.begin(), tim.end()); //w<< at+1 <<';'; for (int j: tim) w s j; w<<e; For (i, 0, tim.size()) { if (i%2 == 0) moves[at]++; else moves[at] += 1 + tim[i]; } int add = adj[at].size()%2; go2(toT[at], curr+add); moves[at] += moves[toT[at]]; } main() { //ifstream cin("test.in"); ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> T >> M; T--; M--; For (i, 1, N) { int a, b; cin >> a >> b; a--; b--; inp[a].pb(b); inp[b].pb(a); } ffi toT[i] = -1; go(M); //ffi {w<< i+1 << ":"; for (int j: adj[i]) w s j+1; w<<e;} go2(M, 0); //ffi w<< i+1 c moves[i]<<e; w<< moves[M]<<e; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 47352 KB | Output is correct |
2 | Correct | 45 ms | 47428 KB | Output is correct |
3 | Correct | 45 ms | 47520 KB | Output is correct |
4 | Correct | 44 ms | 47540 KB | Output is correct |
5 | Correct | 43 ms | 47540 KB | Output is correct |
6 | Correct | 44 ms | 47540 KB | Output is correct |
7 | Correct | 45 ms | 47556 KB | Output is correct |
8 | Correct | 44 ms | 47556 KB | Output is correct |
9 | Correct | 45 ms | 47660 KB | Output is correct |
10 | Correct | 44 ms | 47660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 668 ms | 115032 KB | Output is correct |
2 | Correct | 593 ms | 120564 KB | Output is correct |
3 | Incorrect | 1477 ms | 145796 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 47352 KB | Output is correct |
2 | Correct | 45 ms | 47428 KB | Output is correct |
3 | Correct | 45 ms | 47520 KB | Output is correct |
4 | Correct | 44 ms | 47540 KB | Output is correct |
5 | Correct | 43 ms | 47540 KB | Output is correct |
6 | Correct | 44 ms | 47540 KB | Output is correct |
7 | Correct | 45 ms | 47556 KB | Output is correct |
8 | Correct | 44 ms | 47556 KB | Output is correct |
9 | Correct | 45 ms | 47660 KB | Output is correct |
10 | Correct | 44 ms | 47660 KB | Output is correct |
11 | Incorrect | 45 ms | 145796 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 47352 KB | Output is correct |
2 | Correct | 45 ms | 47428 KB | Output is correct |
3 | Correct | 45 ms | 47520 KB | Output is correct |
4 | Correct | 44 ms | 47540 KB | Output is correct |
5 | Correct | 43 ms | 47540 KB | Output is correct |
6 | Correct | 44 ms | 47540 KB | Output is correct |
7 | Correct | 45 ms | 47556 KB | Output is correct |
8 | Correct | 44 ms | 47556 KB | Output is correct |
9 | Correct | 45 ms | 47660 KB | Output is correct |
10 | Correct | 44 ms | 47660 KB | Output is correct |
11 | Correct | 668 ms | 115032 KB | Output is correct |
12 | Correct | 593 ms | 120564 KB | Output is correct |
13 | Incorrect | 1477 ms | 145796 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |