# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
83807 | 2018-11-10T19:59:26 Z | updown1 | Mousetrap (CEOI17_mousetrap) | C++17 | 640 ms | 115236 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()); 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()); 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); w<< moves[M]<<e; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 47352 KB | Output is correct |
2 | Correct | 44 ms | 47352 KB | Output is correct |
3 | Correct | 43 ms | 47552 KB | Output is correct |
4 | Correct | 44 ms | 47552 KB | Output is correct |
5 | Correct | 43 ms | 47552 KB | Output is correct |
6 | Correct | 43 ms | 47552 KB | Output is correct |
7 | Correct | 43 ms | 47556 KB | Output is correct |
8 | Correct | 47 ms | 47592 KB | Output is correct |
9 | Incorrect | 44 ms | 47648 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 640 ms | 115236 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 47352 KB | Output is correct |
2 | Correct | 44 ms | 47352 KB | Output is correct |
3 | Correct | 43 ms | 47552 KB | Output is correct |
4 | Correct | 44 ms | 47552 KB | Output is correct |
5 | Correct | 43 ms | 47552 KB | Output is correct |
6 | Correct | 43 ms | 47552 KB | Output is correct |
7 | Correct | 43 ms | 47556 KB | Output is correct |
8 | Correct | 47 ms | 47592 KB | Output is correct |
9 | Incorrect | 44 ms | 47648 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 47352 KB | Output is correct |
2 | Correct | 44 ms | 47352 KB | Output is correct |
3 | Correct | 43 ms | 47552 KB | Output is correct |
4 | Correct | 44 ms | 47552 KB | Output is correct |
5 | Correct | 43 ms | 47552 KB | Output is correct |
6 | Correct | 43 ms | 47552 KB | Output is correct |
7 | Correct | 43 ms | 47556 KB | Output is correct |
8 | Correct | 47 ms | 47592 KB | Output is correct |
9 | Incorrect | 44 ms | 47648 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |