結果
問題 | No.2532 Want Play More |
ユーザー | konishi |
提出日時 | 2023-11-06 22:39:03 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,724 bytes |
コンパイル時間 | 2,927 ms |
コンパイル使用メモリ | 256,964 KB |
実行使用メモリ | 31,488 KB |
最終ジャッジ日時 | 2024-09-25 23:09:15 |
合計ジャッジ時間 | 6,386 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 191 ms
16,000 KB |
testcase_02 | WA | - |
testcase_03 | AC | 176 ms
15,616 KB |
testcase_04 | AC | 179 ms
15,548 KB |
testcase_05 | WA | - |
testcase_06 | AC | 153 ms
31,488 KB |
testcase_07 | AC | 8 ms
9,728 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 76 ms
12,468 KB |
testcase_11 | AC | 76 ms
12,416 KB |
testcase_12 | AC | 128 ms
14,224 KB |
testcase_13 | AC | 90 ms
12,928 KB |
testcase_14 | AC | 31 ms
10,672 KB |
testcase_15 | AC | 196 ms
15,744 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 5 ms
9,472 KB |
testcase_21 | AC | 5 ms
9,472 KB |
testcase_22 | AC | 4 ms
9,472 KB |
testcase_23 | AC | 5 ms
9,456 KB |
testcase_24 | AC | 5 ms
9,556 KB |
testcase_25 | AC | 4 ms
9,600 KB |
testcase_26 | AC | 4 ms
9,560 KB |
testcase_27 | AC | 6 ms
9,520 KB |
testcase_28 | AC | 108 ms
16,532 KB |
ソースコード
#include <bits/stdc++.h> //#include<atcoder/all> //using namespace atcoder; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; #define pii pair<int,int> #define pll pair<ll,ll> #define rep(i,num,n) for(int i=num;i<(int)(n);i++) //for_loop #define REP(i,n) for(int i=0;i<(int)(n);i++) #define rrep(i,num,n) for(int i=num-1;i>=(int)(n);i--) //reverse_for> #define in(x,a,b) (a<=x && x<b)//範囲 #define reo return 0 #define all(v) v.begin(),v.end() #define INFI 1010000000 #define INFL 4000000000000000000 //#define ten(x) ((int)1e##x) //#define tenll(x) ((ll)1e##x) #define PI 3.14159265358979 //#define mint modint1000000007 #define mint modint998244353 bool chmin(ll &a,ll b){if(a>b){a=b;return true;}return false;} bool chmax(ll &a,ll b){if(a<b){a=b;return true;}return false;} bool chmin(int &a,int b){if(a>b){a=b;return true;}return false;} bool chmax(int &a,int b){if(a<b){a=b;return true;}return false;} int dx[]={0,0,1,-1};int dy[]={1,-1,0,0}; //int dx[]={1,1,1,0,0,-1,-1,-1},dy[]={1,0,-1,1,-1,1,0,-1}; //---------------------------- vector<int>dpmax(200020,0),dpmin(200020,INFI); vector<bool>used(200020,false); vector<vector<int>>g(200020); int dfs(int pos){ int mi=INFI,ma=-INFI; int dep=0; used[pos]=true; for(auto e:g[pos]){ if(used[e])continue;//探索済み dep=max(dep,dfs(e)+1); ma=max(ma,dep); mi=min(mi,dep); } if(dep==0){//葉 ma=0; mi=0; } dpmax[pos]=ma; dpmin[pos]=mi; return dep; } int main(){ int n;cin>>n; rep(i,1,n){ int a,b;cin>>a>>b;a--,b--; g[a].push_back(b); g[b].push_back(a); } //戦略:先手:最小値の最大化、後手:最大値の最小化 //各頂点について葉までの距離の最小値/最大値がわかればよい。 //方法:木DP //DP[i]→iを根とする部分木において、最小の経路/最大の経路 used[0]=true; dfs(0); int pos=0; int teban=0; used.assign(200010,false); used[0]=true; while (1) { int to=-1; int tmp; if(teban%2==0){//先手,最小値の最大化 tmp=-1; for(auto e:g[pos]){ if(used[e])continue; used[e]=true; if(dpmin[e]>tmp){ to=e; tmp=dpmin[e]; } } }else { tmp=INFI; for(auto e:g[pos]){ if(used[e])continue; used[e]=true; if(dpmax[e]<tmp){ to=e; tmp=dpmax[e]; } } } //遷移 if(to==-1){//葉 break; } pos=to; teban++; } cout<<teban<<endl; //反転// used.assign(200010,false); used[0]=true; pos=0; teban=0; while (1) { int to=-1; int tmp; if(teban%2==1){//後手,最小値の最大化 tmp=-1; for(auto e:g[pos]){ if(used[e])continue; used[e]=true; if(dpmin[e]>tmp){ to=e; tmp=dpmin[e]; } } }else { tmp=INFI; for(auto e:g[pos]){ if(used[e])continue; used[e]=true; if(dpmax[e]<tmp){ to=e; tmp=dpmax[e]; } } } //遷移 if(to==-1){//葉 break; } pos=to; teban++; } cout<<teban<<endl; }