# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
127087 | 2019-07-08T21:35:30 Z | Lawliet | Mousetrap (CEOI17_mousetrap) | C++14 | 1221 ms | 68276 KB |
#include <bits/stdc++.h> #define MAX 1000010 using namespace std; typedef long long int lli; int n; int mouse, trap; int n1, n2; int pai[MAX]; lli dp[MAX]; vector<int> grafo[MAX]; void DFSInit(int i, int p) { for(int g = 0 ; g < grafo[i].size() ; g++) { int prox = grafo[i][g]; if(prox == p) continue; pai[prox] = i; DFSInit(prox , i); } } void DFS(int i) { if(grafo[i].size() == 1 && i != trap) { dp[i] = 0; return; } vector<lli> aux; aux.push_back( 0 ); for(int g = 0 ; g < grafo[i].size() ; g++) { int prox = grafo[i][g]; if(prox == pai[i]) continue; //printf("i = %d chamei %d\n",i,prox); //printf("i = %d prox = %d\n",i,prox); DFS(prox); aux.push_back( dp[prox] ); } sort(aux.begin() , aux.end()); dp[i] = grafo[i].size() - 2 + aux[aux.size() - 2] + 1; //printf("dp(%d) = %lld\n",i,dp[i]); } int main() { scanf("%d %d %d",&n,&trap,&mouse); for(int g = 0 ; g < n - 1 ; g++) { scanf("%d %d",&n1,&n2); grafo[n1].push_back(n2); grafo[n2].push_back(n1); } DFSInit(trap , trap); lli ans = -1; int cur = mouse; while(cur != trap) { //printf("\n\n\n\n"); DFS(trap); //printf("cur = %d\n",cur); /*int aux = pai[cur]; int sum = 0; while(aux != trap) { sum += grafo[aux].size() - 2; aux = pai[aux]; } printf("dp = %d sum = %d\n",dp[cur],sum);*/ for(int g = 0 ; g < grafo[trap].size() ; g++) { int prox = grafo[trap][g]; ans = max(ans , dp[prox]); } //ans = max(ans , dp[cur] + sum); for(int g = 0 ; g < grafo[pai[cur]].size() ; g++) { int prox = grafo[pai[cur]][g]; if(prox == cur) { grafo[pai[cur]].erase(grafo[pai[cur]].begin() + g); break; } } cur = pai[cur]; } printf("%lld\n",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 23800 KB | Output is correct |
2 | Incorrect | 23 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 526 ms | 67036 KB | Output is correct |
2 | Correct | 479 ms | 62744 KB | Output is correct |
3 | Correct | 1212 ms | 68160 KB | Output is correct |
4 | Correct | 540 ms | 46072 KB | Output is correct |
5 | Correct | 1159 ms | 68240 KB | Output is correct |
6 | Correct | 1221 ms | 68276 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 23800 KB | Output is correct |
2 | Incorrect | 23 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 23800 KB | Output is correct |
2 | Incorrect | 23 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |