結果
問題 | No.1424 Ultrapalindrome |
ユーザー | siman |
提出日時 | 2021-12-19 13:44:24 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,059 bytes |
コンパイル時間 | 5,760 ms |
コンパイル使用メモリ | 109,888 KB |
実行使用メモリ | 37,836 KB |
最終ジャッジ日時 | 2023-10-13 18:41:14 |
合計ジャッジ時間 | 5,670 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
28,024 KB |
testcase_01 | AC | 12 ms
27,996 KB |
testcase_02 | AC | 12 ms
28,016 KB |
testcase_03 | AC | 13 ms
28,024 KB |
testcase_04 | AC | 12 ms
28,000 KB |
testcase_05 | AC | 13 ms
28,000 KB |
testcase_06 | AC | 11 ms
27,972 KB |
testcase_07 | AC | 12 ms
28,016 KB |
testcase_08 | WA | - |
testcase_09 | AC | 129 ms
35,088 KB |
testcase_10 | AC | 132 ms
35,092 KB |
testcase_11 | AC | 88 ms
32,920 KB |
testcase_12 | AC | 126 ms
34,592 KB |
testcase_13 | AC | 34 ms
29,996 KB |
testcase_14 | AC | 97 ms
33,368 KB |
testcase_15 | AC | 11 ms
27,992 KB |
testcase_16 | AC | 77 ms
32,444 KB |
testcase_17 | AC | 92 ms
33,204 KB |
testcase_18 | AC | 64 ms
31,292 KB |
testcase_19 | AC | 108 ms
33,276 KB |
testcase_20 | AC | 27 ms
29,308 KB |
testcase_21 | AC | 82 ms
32,236 KB |
testcase_22 | AC | 54 ms
30,700 KB |
testcase_23 | AC | 17 ms
28,608 KB |
testcase_24 | AC | 26 ms
29,128 KB |
testcase_25 | AC | 26 ms
29,120 KB |
testcase_26 | AC | 129 ms
34,224 KB |
testcase_27 | WA | - |
testcase_28 | AC | 104 ms
36,352 KB |
testcase_29 | AC | 100 ms
36,336 KB |
testcase_30 | AC | 87 ms
37,836 KB |
testcase_31 | AC | 96 ms
37,816 KB |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <limits.h> #include <map> #include <queue> #include <set> #include <string.h> #include <vector> using namespace std; typedef long long ll; const int MAX_V = 500000; vector<int> _E[MAX_V]; struct Edge { int to; ll cost; Edge(int to = -1, ll cost = -1) { this->to = to; this->cost = cost; } }; vector <Edge> E[MAX_V]; struct Node { int v; ll cost; Node(int v = -1, ll cost = -1) { this->v = v; this->cost = cost; } }; class Tree { public: int nodeCnt; Tree(int nodeCnt = MAX_V) { this->nodeCnt = nodeCnt; } void addEdge(int from, int to, ll cost = 1) { E[from].push_back(Edge(to, cost)); } vector<int> diameter(int from = 0) { int u = findFarthestVertex(from); int v = findFarthestVertex(u); return findPath(u, v); } ll calcPathCost(vector<int> &path) { ll totalCost = 0; for (int i = 0; i < path.size() - 1; ++i) { int u = path[i]; int v = path[i + 1]; for (int j = 0; j < E[u].size(); ++j) { if (E[u][j].to == v) { totalCost += E[u][j].cost; } } } return totalCost; } vector<int> findPath(int from, int to) { queue <Node> que; que.push(Node(from, 0)); int parent[nodeCnt]; bool visited[nodeCnt]; memset(visited, false, sizeof(visited)); while (!que.empty()) { Node node = que.front(); que.pop(); visited[node.v] = true; if (node.v == to) { vector<int> path; int cur = node.v; while (cur != from) { path.push_back(cur); cur = parent[cur]; } path.push_back(from); reverse(path.begin(), path.end()); return path; } for (int i = 0; i < E[node.v].size(); ++i) { Edge edge = E[node.v][i]; if (visited[edge.to]) continue; parent[edge.to] = node.v; que.push(Node(edge.to, node.cost + edge.cost)); } } return vector<int>(); } private: int findFarthestVertex(int from) { queue <Node> que; que.push(Node(from, 0)); bool visited[MAX_V]; memset(visited, false, sizeof(visited)); ll maxCost = INT_MIN; int farthestV = -1; while (!que.empty()) { Node node = que.front(); que.pop(); if (visited[node.v]) continue; visited[node.v] = true; if (maxCost < node.cost) { maxCost = node.cost; farthestV = node.v; } for (int i = 0; i < E[node.v].size(); ++i) { Edge edge = E[node.v][i]; Node next(edge.to, node.cost + edge.cost); que.push(next); } } return farthestV; } }; int main() { int N; cin >> N; Tree tree; int a, b, c; for (int i = 0; i < N - 1; ++i) { cin >> a >> b; --a; --b; _E[a].push_back(b); _E[b].push_back(a); tree.addEdge(a, b, 1); tree.addEdge(b, a, 1); } vector<int> path = tree.diameter(); queue<int> que; queue<int> d_que; bool visited[N]; memset(visited, false, sizeof(visited)); que.push(path[0]); d_que.push(1); fprintf(stderr, "path size: %d\n", (int) path.size()); while (not que.empty()) { int v = que.front(); int d = d_que.front(); que.pop(); d_que.pop(); if (visited[v]) continue; visited[v] = true; if (d > 1 && _E[v].size() == 1 && path.size() != d) { cout << "No" << endl; return 0; } for (int u : _E[v]) { que.push(u); d_que.push(d + 1); } } memset(visited, false, sizeof(visited)); que.push(path.back()); d_que.push(1); while (not que.empty()) { int v = que.front(); int d = d_que.front(); que.pop(); d_que.pop(); if (visited[v]) continue; visited[v] = true; if (d > 1 && _E[v].size() == 1 && path.size() != d) { cout << "No" << endl; return 0; } for (int u : _E[v]) { que.push(u); d_que.push(d + 1); } } cout << "Yes" << endl; return 0; }