Submission #369272
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
#define MOD 1000000007
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<P,int> PP;
int n;
int ans;
vector<int> G[100000], val[100000];
int dp[100000][2];
bool used[100000];
void dfs(int s){
used[s] = true;
rep(i,G[s].size()){
if(used[G[s][i]]) continue;
dfs(G[s][i]);
if(val[s][i] != 0) ans = max(ans,dp[s][1]+dp[G[s][i]][0]);
if(val[s][i] != 1) ans = max(ans,dp[s][0]+dp[G[s][i]][1]);
if(val[s][i] != 0) dp[s][0] = max(dp[s][0],dp[G[s][i]][0]+1);
if(val[s][i] != 1) dp[s][1] = max(dp[s][1],dp[G[s][i]][1]+1);
}
}
int main(){
scanf("%d",&n);
rep(i,n-1){
int a, b, t;
scanf("%d%d%d",&a,&b,&t);
a--; b--;
if(t == 2){
G[a].pb(b);
G[b].pb(a);
val[a].pb(2);
val[b].pb(2);
} else{
G[a].pb(b);
G[b].pb(a);
val[a].pb(1);
val[b].pb(0);
}
}
dfs(0);
printf("%d\n",ans);
}
Submission Info
Submission Time
2015-03-27 00:51:58+0900
Task
D - Longest Path
User
gasin
Language
C++ (GCC 4.9.2)
Score
100
Code Size
1053 Byte
Status
AC
Exec Time
163 ms
Memory
16864 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:32:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:35:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&a,&b,&t);
^
Judge Result
Set Name
All
Score / Max Score
100 / 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
37 ms
5404 KB
00-sample-01.txt
AC
33 ms
5408 KB
10-path-00.txt
AC
33 ms
5412 KB
10-path-01.txt
AC
163 ms
16864 KB
10-path-02.txt
AC
60 ms
8352 KB
10-path-03.txt
AC
71 ms
8988 KB
10-path-04.txt
AC
110 ms
12456 KB
20-path_special-00.txt
AC
153 ms
16796 KB
20-path_special-01.txt
AC
152 ms
15644 KB
20-path_special-02.txt
AC
152 ms
15392 KB
30-star-00.txt
AC
117 ms
12560 KB
30-star-01.txt
AC
35 ms
5664 KB
30-star-02.txt
AC
65 ms
8600 KB
30-star-03.txt
AC
70 ms
8684 KB
40-binary-00.txt
AC
149 ms
12580 KB
40-binary-01.txt
AC
132 ms
11940 KB
40-binary-02.txt
AC
33 ms
5656 KB
40-binary-03.txt
AC
115 ms
10788 KB
40-binary-04.txt
AC
36 ms
5788 KB
50-random-00.txt
AC
143 ms
12832 KB
50-random-01.txt
AC
68 ms
7968 KB
50-random-02.txt
AC
98 ms
9900 KB
50-random-03.txt
AC
79 ms
8732 KB
50-random-04.txt
AC
85 ms
9116 KB
50-random-05.txt
AC
135 ms
12320 KB
50-random-06.txt
AC
40 ms
5868 KB
50-random-07.txt
AC
48 ms
6568 KB
50-random-08.txt
AC
129 ms
11936 KB
50-random-09.txt
AC
100 ms
10076 KB
50-random-10.txt
AC
94 ms
9764 KB
50-random-11.txt
AC
49 ms
6692 KB
50-random-12.txt
AC
136 ms
12316 KB