結果
問題 | No.2532 Want Play More |
ユーザー | konishi |
提出日時 | 2023-11-06 23:11:26 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,020 bytes |
コンパイル時間 | 3,336 ms |
コンパイル使用メモリ | 256,560 KB |
実行使用メモリ | 28,336 KB |
最終ジャッジ日時 | 2024-09-25 23:12:41 |
合計ジャッジ時間 | 7,411 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
9,472 KB |
testcase_01 | AC | 270 ms
15,872 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | AC | 251 ms
15,512 KB |
testcase_05 | WA | - |
testcase_06 | AC | 162 ms
28,336 KB |
testcase_07 | AC | 8 ms
9,600 KB |
testcase_08 | AC | 11 ms
9,700 KB |
testcase_09 | AC | 10 ms
9,728 KB |
testcase_10 | AC | 100 ms
12,416 KB |
testcase_11 | AC | 93 ms
12,380 KB |
testcase_12 | AC | 173 ms
14,208 KB |
testcase_13 | AC | 114 ms
13,056 KB |
testcase_14 | AC | 35 ms
10,752 KB |
testcase_15 | WA | - |
testcase_16 | AC | 184 ms
14,848 KB |
testcase_17 | AC | 10 ms
9,600 KB |
testcase_18 | WA | - |
testcase_19 | AC | 208 ms
14,976 KB |
testcase_20 | AC | 6 ms
9,460 KB |
testcase_21 | AC | 6 ms
9,600 KB |
testcase_22 | AC | 6 ms
9,472 KB |
testcase_23 | AC | 6 ms
9,600 KB |
testcase_24 | AC | 5 ms
9,600 KB |
testcase_25 | AC | 5 ms
9,472 KB |
testcase_26 | AC | 5 ms
9,528 KB |
testcase_27 | AC | 5 ms
9,464 KB |
testcase_28 | AC | 118 ms
16,468 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 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); } if(dep==0){//葉 ma=0; } dpmax[pos]=ma; return dep; } int dfs2(int pos){//最小値 int mi=INFI; int dep=INFI; used[pos]=true; for(auto e:g[pos]){ if(used[e])continue;//探索済み dep=min(dep,dfs2(e)+1); mi=min(mi,dep); } if(dep==INFI){//葉 mi=0; } dpmin[pos]=mi; return mi; } 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); used.assign(200010,false); used[0]=true; dfs2(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; }