Submission #1414883
Source Code Expand
#include<bits/stdc++.h> using namespace std; vector<int> e[2][100000]; int mem[2][100000]; int dfs(int p,int f,int pr){ int res=0; if(f==-1){ int a=0,b=0; for(int i=0;i<e[0][p].size();i++) a=max(a,dfs(e[0][p][i] , 0,p) ); for(int i=0;i<e[1][p].size();i++) b=max(b,dfs(e[1][p][i] , 1,p) ); return max(a,b); } else { if(mem[f][p]!=-1)return mem[f][p]; for(int i=0;i<e[f][p].size();i++) if(e[f][p][i]!=pr) res=max(res,dfs(e[f][p][i],f,p)); } return mem[f][p]=res+1; } int main(){ int n; int a,b,t; cin>>n; int u[100000]={}; for(int i=0;i<n-1;i++){ cin>>a>>b>>t; a--,b--; u[a]++,u[b]++; e[0][a].push_back(b); e[1][b].push_back(a); if(t==2) { e[0][b].push_back(a); e[1][a].push_back(b); } } memset(mem,-1,sizeof(mem)); int ans=0; for(int i=0;i<n;i++){ if(u[i]==1) ans=max(ans,dfs(i,-1,-1)); } cout<<ans-1<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Longest Path |
User | aizu_b |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1048 Byte |
Status | WA |
Exec Time | 157 ms |
Memory | 20224 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00-sample-00.txt, 00-sample-01.txt, 10-path-00.txt, 10-path-01.txt, 10-path-02.txt, 10-path-03.txt, 10-path-04.txt, 20-path_special-00.txt, 20-path_special-01.txt, 20-path_special-02.txt, 30-star-00.txt, 30-star-01.txt, 30-star-02.txt, 30-star-03.txt, 40-binary-00.txt, 40-binary-01.txt, 40-binary-02.txt, 40-binary-03.txt, 40-binary-04.txt, 50-random-00.txt, 50-random-01.txt, 50-random-02.txt, 50-random-03.txt, 50-random-04.txt, 50-random-05.txt, 50-random-06.txt, 50-random-07.txt, 50-random-08.txt, 50-random-09.txt, 50-random-10.txt, 50-random-11.txt, 50-random-12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample-00.txt | AC | 4 ms | 6144 KB |
00-sample-01.txt | AC | 4 ms | 6144 KB |
10-path-00.txt | AC | 4 ms | 6144 KB |
10-path-01.txt | WA | 126 ms | 11904 KB |
10-path-02.txt | WA | 30 ms | 7552 KB |
10-path-03.txt | WA | 40 ms | 8064 KB |
10-path-04.txt | WA | 82 ms | 9984 KB |
20-path_special-00.txt | AC | 139 ms | 20224 KB |
20-path_special-01.txt | AC | 157 ms | 20224 KB |
20-path_special-02.txt | WA | 113 ms | 10752 KB |
30-star-00.txt | AC | 114 ms | 11376 KB |
30-star-01.txt | AC | 6 ms | 6272 KB |
30-star-02.txt | AC | 49 ms | 8440 KB |
30-star-03.txt | AC | 51 ms | 8568 KB |
40-binary-00.txt | AC | 135 ms | 11520 KB |
40-binary-01.txt | AC | 124 ms | 11136 KB |
40-binary-02.txt | WA | 6 ms | 6272 KB |
40-binary-03.txt | AC | 107 ms | 10240 KB |
40-binary-04.txt | AC | 8 ms | 6272 KB |
50-random-00.txt | WA | 135 ms | 11520 KB |
50-random-01.txt | WA | 42 ms | 7936 KB |
50-random-02.txt | WA | 81 ms | 9472 KB |
50-random-03.txt | WA | 58 ms | 8576 KB |
50-random-04.txt | WA | 65 ms | 8832 KB |
50-random-05.txt | WA | 126 ms | 11264 KB |
50-random-06.txt | WA | 10 ms | 6400 KB |
50-random-07.txt | WA | 21 ms | 6912 KB |
50-random-08.txt | WA | 116 ms | 10880 KB |
50-random-09.txt | WA | 84 ms | 9472 KB |
50-random-10.txt | WA | 78 ms | 9344 KB |
50-random-11.txt | AC | 22 ms | 7040 KB |
50-random-12.txt | WA | 127 ms | 11264 KB |