結果
問題 | No.1424 Ultrapalindrome |
ユーザー |
|
提出日時 | 2021-03-12 21:48:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 852 bytes |
コンパイル時間 | 1,593 ms |
コンパイル使用メモリ | 171,428 KB |
実行使用メモリ | 16,768 KB |
最終ジャッジ日時 | 2024-10-14 16:10:50 |
合計ジャッジ時間 | 2,928 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Graph=vector<vector<int>>; void rep(int v,int pv,int d,vector<int> &res,Graph &g){ res[v]=d; for(auto &nx : g[v]){ if(nx==pv){continue;} rep(nx,v,d+1,res,g); } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; Graph g(n); for(int i=1;i<n;i++){ int u,v; cin >> u >> v; u--;v--; g[u].push_back(v); g[v].push_back(u); } int bas=-1; for(int i=0;i<n;i++){ if(g[i].size()>2){ if(bas==-1){bas=i;} else{cout << "No\n";return 0;} } } if(bas==-1){cout << "Yes\n";return 0;} vector<int> res(n); rep(bas,-1,0,res,g); int ld=-1; for(int i=0;i<n;i++){ if(g[i].size()==1){ if(ld==-1){ld=res[i];} else if(ld!=res[i]){cout << "No\n";return 0;} } } cout << "Yes\n"; return 0; }