結果
問題 |
No.1424 Ultrapalindrome
|
ユーザー |
![]() |
提出日時 | 2021-03-14 19:38:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,511 bytes |
コンパイル時間 | 989 ms |
コンパイル使用メモリ | 96,780 KB |
実行使用メモリ | 10,428 KB |
最終ジャッジ日時 | 2024-11-06 08:46:46 |
合計ジャッジ時間 | 3,210 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
/* -*- coding: utf-8 -*- * * 1424.cc: No.1424 Ultrapalindrome - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100000; /* typedef */ typedef vector<int> vi; /* global variables */ vi nbrs[MAX_N]; int ps[MAX_N], ds[MAX_N], cis[MAX_N]; /* subroutines */ /* main */ int main() { int n; scanf("%d", &n); for (int i = 1; i < n; i++) { int a, b; scanf("%d%d", &a, &b); a--, b--; nbrs[a].push_back(b); nbrs[b].push_back(a); } int ln = 0, rt = -1; for (int u = 0; u < n; u++) { int szu = nbrs[u].size(); if (szu == 1) ln++; else if (szu > 2) { if (rt < 0) rt = u; else { puts("No"); return 0; } } } if (ln == 2) { puts("Yes"); return 0; } int ld = -1; ps[rt] = -1, ds[rt] = 0; for (int u = rt; u >= 0;) { vi &nbru = nbrs[u]; int &ciu = cis[u]; if (ciu < nbru.size() && nbru[ciu] == ps[u]) ciu++; if (ciu < nbru.size()) { int v = nbru[ciu++]; ps[v] = u, ds[v] = ds[u] + 1; if (nbrs[v].size() == 1) { if (ld < 0) ld = ds[v]; else if (ld != ds[v]) { puts("No"); return 0; } } u = v; } else { u = ps[u]; } } puts("Yes"); return 0; }