結果
問題 | No.1295 木と駒 |
ユーザー | chocorusk |
提出日時 | 2020-11-20 23:09:44 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 310 ms / 2,000 ms |
コード長 | 4,062 bytes |
コンパイル時間 | 1,452 ms |
コンパイル使用メモリ | 139,360 KB |
実行使用メモリ | 37,948 KB |
最終ジャッジ日時 | 2023-09-30 19:57:15 |
合計ジャッジ時間 | 14,071 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,932 KB |
testcase_01 | AC | 4 ms
5,648 KB |
testcase_02 | AC | 4 ms
5,716 KB |
testcase_03 | AC | 3 ms
5,640 KB |
testcase_04 | AC | 3 ms
5,712 KB |
testcase_05 | AC | 3 ms
5,960 KB |
testcase_06 | AC | 4 ms
5,800 KB |
testcase_07 | AC | 3 ms
5,720 KB |
testcase_08 | AC | 3 ms
5,704 KB |
testcase_09 | AC | 3 ms
5,692 KB |
testcase_10 | AC | 3 ms
5,936 KB |
testcase_11 | AC | 3 ms
5,816 KB |
testcase_12 | AC | 3 ms
5,780 KB |
testcase_13 | AC | 3 ms
5,656 KB |
testcase_14 | AC | 278 ms
9,500 KB |
testcase_15 | AC | 283 ms
9,512 KB |
testcase_16 | AC | 281 ms
9,656 KB |
testcase_17 | AC | 270 ms
9,556 KB |
testcase_18 | AC | 277 ms
9,484 KB |
testcase_19 | AC | 296 ms
14,336 KB |
testcase_20 | AC | 286 ms
37,580 KB |
testcase_21 | AC | 296 ms
21,196 KB |
testcase_22 | AC | 301 ms
14,860 KB |
testcase_23 | AC | 277 ms
25,996 KB |
testcase_24 | AC | 280 ms
26,124 KB |
testcase_25 | AC | 253 ms
15,220 KB |
testcase_26 | AC | 237 ms
37,848 KB |
testcase_27 | AC | 238 ms
37,788 KB |
testcase_28 | AC | 309 ms
27,328 KB |
testcase_29 | AC | 237 ms
37,860 KB |
testcase_30 | AC | 238 ms
37,948 KB |
testcase_31 | AC | 239 ms
37,864 KB |
testcase_32 | AC | 297 ms
37,580 KB |
testcase_33 | AC | 261 ms
9,652 KB |
testcase_34 | AC | 281 ms
9,472 KB |
testcase_35 | AC | 257 ms
9,636 KB |
testcase_36 | AC | 267 ms
9,624 KB |
testcase_37 | AC | 263 ms
9,632 KB |
testcase_38 | AC | 265 ms
9,540 KB |
testcase_39 | AC | 262 ms
9,560 KB |
testcase_40 | AC | 260 ms
9,632 KB |
testcase_41 | AC | 297 ms
14,548 KB |
testcase_42 | AC | 310 ms
14,492 KB |
testcase_43 | AC | 301 ms
14,388 KB |
testcase_44 | AC | 309 ms
14,368 KB |
testcase_45 | AC | 307 ms
14,440 KB |
testcase_46 | AC | 307 ms
14,340 KB |
testcase_47 | AC | 301 ms
14,320 KB |
testcase_48 | AC | 301 ms
14,240 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; int n; vector<int> g[100010]; int mn[100010]; bool dp[100010]; bool dp2[100010];//xの親側行って帰ってこれるか bool ep[100010], ep2[100010];//xの親側行けるか int par[100010]; void dfs(int x, int p){ dp[x]=1; par[x]=p; int mn=1e9, mx=-1; for(auto y:g[x]){ if(y==p) continue; mn=min(mn, y), mx=max(mx, y); dfs(y, x); if(!dp[y] || g[y][0]!=x){ dp[x]=0; } } if(mx==-1){ ep[x]=1; return; } bool ok1=ep[mx]; for(auto y:g[x]){ if(y==p) continue; if(mx!=y && (!dp[y] || g[y][0]!=x)){ ok1=0; } } bool ok2=ep[mn]; if(mn>par[x]) ok2=0; for(auto y:g[x]){ if(y==p) continue; if(mn!=y && (!dp[y] || g[y][0]!=x)){ ok2=0; } } if(ok1 || ok2) ep[x]=1; } void dfs2(int x, int p){ int y0=g[x][0]; int cnt=0; for(auto y:g[x]){ if(y==p){ if(dp2[x]) cnt++; }else if(y!=y0){ if(dp[y] && g[y][0]==x) cnt++; } } if(y0!=p && cnt==(int)g[x].size()-1){ dp2[y0]=1; } set<int> st; for(auto y:g[x]) st.insert(y); cnt=0; for(auto y:g[x]){ if(y==p){ if(dp2[x]) cnt++; }else{ if(dp[y] && g[y][0]==x) cnt++; } } for(auto y:g[x]){ if(y==p) continue; int cnt1=0, cnt2=0; if(y==p){ if(dp2[x]) cnt1++; }else{ if(dp[y] && g[y][0]==x) cnt1++; } st.erase(y); int mx=*st.rbegin(); if(mx==p){ if(dp2[x]) cnt2++; }else{ if(dp[mx] && g[mx][0]==x) cnt2++; } bool e=0; if(mx==par[x]) e=ep2[x]; else e=ep[mx]; if(cnt-cnt1-cnt2==(int)g[x].size()-2 && e){ ep2[y]=1; } int mn=*st.begin(); cnt2=0; if(mn==p){ if(dp2[x]) cnt2++; }else{ if(dp[mn] && g[mn][0]==x) cnt2++; } e=0; if(mn==par[x]) e=ep2[x]; else e=ep[mn]; if(mn<y && cnt-cnt1-cnt2==(int)g[x].size()-2 && e){ ep2[y]=1; } st.insert(y); } for(auto y:g[x]){ if(y!=p) dfs2(y, x); } } int main() { cin>>n; for(int i=0; i<n-1; i++){ int a, b; cin>>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } if(n==2){ cout<<"Yes"<<endl; cout<<"Yes"<<endl; return 0; } int r=0; for(int i=0; i<n; i++){ sort(g[i].begin(), g[i].end()); if(g[i].size()>1) r=i; } dfs(r, -1); dfs2(r, -1); for(int x=0; x<n; x++){ bool ok1=1; if(g[x][0]==par[x]){ ok1=ep2[x]; }else{ ok1=ep[g[x][0]]; } for(int i=1; i<g[x].size(); i++){ int y=g[x][i]; if(y==par[x]){ if(!dp2[x]) ok1=0; }else{ if(!dp[y] || g[y][0]!=x) ok1=0; } } bool ok2=1; if(g[x].back()==par[x]){ ok2=ep2[x]; }else{ ok2=ep[g[x].back()]; } for(int i=0; i<(int)g[x].size()-1; i++){ int y=g[x][i]; if(y==par[x]){ if(!dp2[x]) ok2=0; }else{ if(!dp[y] || g[y][0]!=x) ok2=0; } } if(ok1 || ok2) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }