Submission #1351541
Source Code Expand
#include<iostream> #include<vector> #include<queue> using namespace std; vector<pair<int, int>>X[1 << 17], Y[1 << 17]; int dist[1 << 17], N, A, B, C, root; queue<int>Q; int main() { cin >> N; for (int i = 0; i < N - 1; i++) { cin >> A >> B >> C; X[A].push_back(make_pair(B, C)); Y[B].push_back(make_pair(A, C)); } for (int i = 0; i < N; i++) { if (Y[i].size() == 0) { root = i; } } for (int i = 0; i < N; i++) { dist[i] = 1145141919; }Q.push(root); dist[root] = 0; while (!Q.empty()) { int a1 = Q.front(); Q.pop(); for (int i = 0; i < X[a1].size(); i++) { int to = X[a1][i].first, a2 = X[a1][i].second; if (dist[to] == 1145141919) { dist[to] = dist[a1] + a2; Q.push(to); } } } int maxn = 0, maxid = 0; for (int i = 0; i < N; i++) { if (maxn < dist[i]) { maxn = dist[i]; maxid = i; } }Q.push(maxid); for (int i = 0; i < N; i++) { dist[i] = 1145141919; }dist[maxid] = 0; while (!Q.empty()) { int a1 = Q.front(); Q.pop(); maxn = 0; maxid = 0; for (int i = 0; i < X[a1].size(); i++) { int to = X[a1][i].first, a2 = X[a1][i].second; if (dist[to] > dist[a1] + a2) { dist[to] = dist[a1] + a2; Q.push(to); } } for (int i = 0; i < Y[a1].size(); i++) { int to = Y[a1][i].first, a2 = Y[a1][i].second; if (dist[to] > dist[a1] + a2) { dist[to] = dist[a1] + a2; Q.push(to); } } } for (int i = 0; i < N; i++) { if (maxn < dist[i]) { maxn = dist[i]; maxid = i; } } cout << maxn+1 << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - Problem on Tree |
User | E869120 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1610 Byte |
Status | WA |
Exec Time | 78 ms |
Memory | 10868 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | WA | 3 ms | 6400 KB |
sample_02.txt | WA | 3 ms | 6400 KB |
subtask1_01.txt | WA | 62 ms | 10108 KB |
subtask1_02.txt | WA | 49 ms | 9340 KB |
subtask1_03.txt | WA | 22 ms | 7680 KB |
subtask1_04.txt | WA | 28 ms | 8064 KB |
subtask1_05.txt | WA | 34 ms | 8320 KB |
subtask1_06.txt | WA | 6 ms | 6656 KB |
subtask1_07.txt | WA | 74 ms | 10660 KB |
subtask1_08.txt | WA | 22 ms | 7680 KB |
subtask1_09.txt | WA | 45 ms | 9212 KB |
subtask1_10.txt | WA | 60 ms | 9772 KB |
subtask1_11.txt | WA | 29 ms | 8064 KB |
subtask1_12.txt | WA | 12 ms | 7040 KB |
subtask1_13.txt | WA | 8 ms | 6784 KB |
subtask1_14.txt | WA | 8 ms | 6784 KB |
subtask1_15.txt | WA | 74 ms | 10868 KB |
subtask1_16.txt | WA | 75 ms | 10868 KB |
subtask1_17.txt | WA | 76 ms | 10868 KB |
subtask1_18.txt | WA | 72 ms | 10868 KB |
subtask1_19.txt | WA | 74 ms | 10868 KB |
subtask1_20.txt | WA | 74 ms | 10868 KB |
subtask1_21.txt | WA | 74 ms | 10868 KB |
subtask1_22.txt | WA | 75 ms | 10868 KB |
subtask1_23.txt | WA | 72 ms | 10868 KB |
subtask1_24.txt | WA | 76 ms | 10868 KB |
subtask1_25.txt | WA | 75 ms | 10696 KB |
subtask1_26.txt | WA | 75 ms | 10868 KB |
subtask1_27.txt | WA | 75 ms | 10868 KB |
subtask1_28.txt | WA | 78 ms | 10868 KB |
subtask1_29.txt | WA | 73 ms | 10868 KB |
subtask1_30.txt | WA | 73 ms | 10868 KB |
subtask1_31.txt | WA | 74 ms | 10868 KB |
subtask1_32.txt | WA | 74 ms | 10868 KB |
subtask1_33.txt | WA | 76 ms | 10696 KB |
subtask1_34.txt | WA | 78 ms | 10868 KB |
subtask1_35.txt | WA | 74 ms | 10868 KB |
subtask1_36.txt | WA | 73 ms | 10868 KB |
subtask1_37.txt | WA | 74 ms | 10868 KB |
subtask1_38.txt | WA | 74 ms | 10868 KB |
subtask1_39.txt | WA | 75 ms | 10868 KB |