結果

問題 No.2532 Want Play More
ユーザー rieaaddlreiuurieaaddlreiuu
提出日時 2024-05-24 13:44:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,812 bytes
コンパイル時間 1,870 ms
コンパイル使用メモリ 178,592 KB
実行使用メモリ 47,916 KB
最終ジャッジ日時 2024-05-24 13:44:30
合計ジャッジ時間 7,227 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 293 ms
26,564 KB
testcase_02 AC 325 ms
26,632 KB
testcase_03 AC 288 ms
25,620 KB
testcase_04 AC 278 ms
25,588 KB
testcase_05 WA -
testcase_06 AC 212 ms
47,916 KB
testcase_07 AC 5 ms
6,940 KB
testcase_08 AC 9 ms
6,940 KB
testcase_09 AC 7 ms
6,940 KB
testcase_10 AC 120 ms
14,208 KB
testcase_11 AC 116 ms
13,948 KB
testcase_12 AC 217 ms
20,732 KB
testcase_13 AC 149 ms
16,000 KB
testcase_14 AC 39 ms
7,552 KB
testcase_15 WA -
testcase_16 AC 251 ms
22,752 KB
testcase_17 AC 7 ms
6,940 KB
testcase_18 AC 175 ms
18,348 KB
testcase_19 AC 246 ms
23,276 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 RE -
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 124 ms
24,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <regex>
#include <algorithm>
using namespace std;
/*
[問題メモ]
v parent
iの親がparent[i]

v<v> child
iの子がparent[i]

*/
void create_tree(int v,vector<vector<int>> &connected,vector<int> &parent,vector<vector<int>> &child){
    for(int i=0;i<connected[v].size();i++){
        if(parent[v] != connected[v][i]){
            parent[connected[v][i]] = v;
            child[v].push_back(connected[v][i]);
            create_tree(connected[v][i],connected,parent,child);
        }
    }
}

int max_depth(vector<int> &parent,vector<vector<int>> &child,int n,vector<int> &memo,vector<int> &memo_index){
	if(child[n].empty()){
        memo[n] = 0;
        memo_index[n] = -1;
		return 0;
	}
	int m = 0,max = 0;
	for(int i=0;i<child[n].size();i++){
		m = max_depth(parent,child,child[n][i],memo,memo_index);
		if(m > max){
            memo_index[n] = i;
			max = m;
		}
	}
    memo[n] = max+1;
	return max+1;
}

int min_depth(vector<int> &parent,vector<vector<int>> &child,int n,vector<int> &memo,vector<int> &memo_index){
	if(child[n].empty()){
		memo[n] = 0;
        memo_index[n] = -1;
		return 0;
	}
	int m = 0,min = 998244353;
	for(int i=0;i<child[n].size();i++){
		m = min_depth(parent,child,child[n][i],memo,memo_index);
		if(m < min){
            memo_index[n] = i;
			min = m;
		}
	}
    memo[n] = min+1;
	return min+1;
}

int main() {
    int N,a,b;
    cin >> N;
    vector<int> parent(N);
    vector<vector<int>> child(N);
    vector<vector<int>> connected(N);
    for(int i=0;i<N;i++){
        cin >> a;
        cin >> b;
        connected[a-1].push_back(b-1);
        connected[b-1].push_back(a-1);
    }
    create_tree(0,connected,parent,child);
    for(int i=0;i<N;i++){
        sort(child[i].begin(),child[i].end());
    }
    vector<int> max_memo(N);
    vector<int> min_memo(N);
    vector<int> max_index_memo(N);
    vector<int> min_index_memo(N);
    max_depth(parent,child,0,max_memo,max_index_memo);
    min_depth(parent,child,0,min_memo,min_index_memo);

    //ゲームスタート
    //Halcは最小深さが最大のとこに行く
    //Sappは最大深さが最小のとこに行く
    //Halcが先だとどうなるか
    int current_node = 0, turn = 0;
    int m = 0,index = 0;
    int sss = 0;
    vector<int> child_child;
    while(!child[current_node].empty()){
        if(turn % 2 == 0){
            //Halcのターン
            m = 0;
            for(int i=0;i<child[current_node].size();i++){
                if(m < min_memo[child[current_node][i]]){
                    m = min_memo[child[current_node][i]];
                    index = i;
                }
            }

            child_child = child[child[current_node][max_index_memo[current_node]]];
            for(sss=0;sss<child_child.size();sss++){
                if(max_memo[child_child[sss]] < max_memo[current_node] -2 ){
                    break;
                }
            }
            if(child_child.size() == sss){
                current_node = child[current_node][max_index_memo[current_node]];
            } else {
                current_node = child[current_node][index];
            }
        }
        if(turn % 2 == 1){
            //Sappのターン
            m = 998244353;
            for(int i=0;i<child[current_node].size();i++){
                if(m > max_memo[child[current_node][i]]){
                    m = max_memo[child[current_node][i]];
                    index = i;
                }
            }

            child_child = child[child[current_node][min_index_memo[current_node]]];
            for(sss=0;sss<child_child.size();sss++){
                if(min_memo[child_child[sss]] > min_memo[current_node] -2 ){
                    break;
                }
            }
            if(child_child.size() == sss){
                current_node = child[current_node][min_index_memo[current_node]];
            } else {
                current_node = child[current_node][index];
            }
        }
        turn++;
    }
    cout << turn << endl;
    turn = 0;
    current_node = 0;
    while(!child[current_node].empty()){
        if(turn % 2 == 1){
            //Halcのターン
            m = 0;
            for(int i=0;i<child[current_node].size();i++){
                if(m < min_memo[child[current_node][i]]){
                    m = min_memo[child[current_node][i]];
                    index = i;
                }
            }

            child_child = child[child[current_node][max_index_memo[current_node]]];
            for(sss=0;sss<child_child.size();sss++){
                if(max_memo[child_child[sss]] < max_memo[current_node] -2 ){
                    break;
                }
            }
            if(child_child.size() == sss){
                current_node = child[current_node][max_index_memo[current_node]];
            } else {
                current_node = child[current_node][index];
            }
        }
        if(turn % 2 == 0){
            //Sappのターン
            m = 998244353;
            for(int i=0;i<child[current_node].size();i++){
                if(m > max_memo[child[current_node][i]]){
                    m = max_memo[child[current_node][i]];
                    index = i;
                }
            }

            child_child = child[child[current_node][min_index_memo[current_node]]];
            for(sss=0;sss<child_child.size();sss++){
                if(min_memo[child_child[sss]] > min_memo[current_node] -2 ){
                    break;
                }
            }
            if(child_child.size() == sss){
                current_node = child[current_node][min_index_memo[current_node]];
            } else {
                current_node = child[current_node][index];
            }
        }
        turn++;
    }
    cout << turn << endl;
    return 0;
}
0