結果
問題 |
No.1424 Ultrapalindrome
|
ユーザー |
![]() |
提出日時 | 2021-03-12 23:29:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,465 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 203,084 KB |
最終ジャッジ日時 | 2025-01-19 15:49:36 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 WA * 1 |
ソースコード
#define rep(i, n) for (int i = 0; i < (int)(n); i++) #define ALL(v) v.begin(), v.end() typedef long long ll; #include <bits/stdc++.h> using namespace std; const int INF=1e9; struct Edge{ int to; int w; Edge(int to,ll w) : to(to),w(w) {} }; using Graph=vector<vector<Edge>>; using pli=pair<ll,int>; int dist[100010]; int dim[100010]; template<class T> bool chmin(T& a,T b){ if(a>b){ a=b; return true; } return false; } int main(){ int n; cin>>n; Graph G(n); rep(i,n-1){ int a,b; cin>>a>>b; a--,b--; G[a].push_back(Edge(b,1)); G[b].push_back(Edge(a,1)); } rep(i,n) dim[i]=G[i].size(); int cnt=0; int mid; rep(i,n){ if(dim[i]>2){ cnt++; mid=i; } } if(cnt>2){ cout<<"No"<<endl; return 0; } else if(cnt==0){ cout<<"Yes"<<endl; return 0; } int s=mid; rep(i,n) dist[i]=INF; dist[s]=0; priority_queue<pli,vector<pli>,greater<pli>> que; que.push({dist[s],s}); while(!que.empty()){ int v=que.top().second; ll d=que.top().first; que.pop(); if(d>dist[v]) continue; for(auto e:G[v]){ if(chmin(dist[e.to],dist[v]+e.w)){ que.push({dist[e.to],e.to}); } } } bool b=true; int tmp=-1; rep(i,n){ if(dim[i]!=1) continue; if(tmp==-1) tmp=dist[i]; else if(dist[i]!=tmp){ b=false; break; } } if(b) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }