結果

問題 No.2532 Want Play More
コンテスト
ユーザー rieaaddlreiuu
提出日時 2024-05-24 13:44:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,812 bytes
コンパイル時間 2,024 ms
コンパイル使用メモリ 178,140 KB
実行使用メモリ 47,744 KB
最終ジャッジ日時 2024-12-20 19:22:35
合計ジャッジ時間 6,911 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other AC * 24 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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