Submission #1024906
Source Code Expand
#include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <climits> #include <ctime> #include <cassert> using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define all(v) begin(v), end(v) #define pb(a) push_back(a) #define fr first #define sc second #define INF 2000000000 #define int long long int #define X real() #define Y imag() #define EPS (1e-10) #define EQ(a,b) (abs((a) - (b)) < EPS) #define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) ) #define LE(n, m) ((n) < (m) + EPS) #define LEQ(n, m) ((n) <= (m) + EPS) #define GE(n, m) ((n) + EPS > (m)) #define GEQ(n, m) ((n) + EPS >= (m)) typedef vector<int> VI; typedef vector<VI> MAT; typedef pair<int, int> pii; typedef long long ll; typedef complex<double> P; typedef pair<P, P> L; typedef pair<P, double> C; int dy[]={0, 0, 1, -1}; int dx[]={1, -1, 0, 0}; int const MOD = 1000000007; namespace std { bool operator<(const P& a, const P& b) { return a.X != b.X ? a.X < b.X : a.Y < b.Y; } } // 移動元と行先と辺のコストを記録する構造体 struct Edge { int from, to, cost; Edge(int s, int d) : to(s), cost(d) {} Edge(int f, int s, int d) : from(f), to(s), cost(d) {} bool operator<(const Edge &e) const { return cost < e.cost; } bool operator>(const Edge &e) const { return cost > e.cost; } }; // 1つの頂点について、辺の情報を保存するために必要な vector // Edgesのサイズは各頂点から出る辺の数に等しくなる typedef vector<Edge> Edges; // 辺の情報を保存する vector // Graphのサイズは頂点の数に等しいので、 V である。 typedef vector<Edges> Graph; // DP テーブル // dp[i][j] := vector< vector<int> > dp; // Graph, vertex, prev int dfs(Graph &G, int v, int p) { int res = 0; for(auto e : G[v]) { if(e.to == p) continue; res = max(res, dfs(G, e.to, v)); // conditional branch if(e.cost == 0 || e.cost == 2) { // v -> e.to res = max(res, dp[0][v] + dp[1][e.to]); dp[0][v] = max(dp[0][v], dp[0][e.to] + 1); } if(e.cost == 1 || e.cost == 2) { // v <- e.to res = max(res, dp[1][v] + dp[0][e.to]); dp[1][v] = max(dp[1][v], dp[1][e.to] + 1); } } return res; } signed main() { int n; cin >> n; int a, b, t; Graph G(n); rep(i,0,n-1) { cin >> a >> b >> t; a--; b--; // type 0: a → b // type 1: a ← b // type 2: a ⇔ b if(t == 1) { G[a].pb(Edge(b,0)); G[b].pb(Edge(a,1)); } else { G[a].pb(Edge(b,2)); G[b].pb(Edge(a,2)); } } dp.assign(2, vector<int>(n)); cout << dfs(G, 0, -1) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Longest Path |
User | tsutaj |
Language | C++ (GCC 4.9.2) |
Score | 0 |
Code Size | 3323 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘long long int dfs(Graph&, long long int, long long int)’: ./Main.cpp:91:14: error: ‘e’ does not name a type for(auto e : G[v]) { ^ ./Main.cpp:107:5: error: expected ‘;’ before ‘return’ return res; ^ ./Main.cpp:107:5: error: expected primary-expression before ‘return’ ./Main.cpp:107:5: error: expected ‘;’ before ‘return’ ./Main.cpp:107:5: error: expected primary-expression before ‘return’ ./Main.cpp:107:5: error: expected ‘)’ before ‘return’