結果

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

ソースコード

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());
    }
    /*for(int i=0;i<child.size();i++){
    	cout << i << "のchild : ";
    	for(int j=0;j<child[i].size();j++){
    		cout << child[i][j] << " ";
    	}
    	cout << endl;
    }*/
    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);
    /*for(int i=0;i<N;i++){
        cout << "頂点" << i << " 最大深さ : " << max_memo[i] << "(index : " << max_index_memo[i] << ")" << endl;
    }
    for(int i=0;i<N;i++){
    	cout << "頂点" << i << " 最小深さ : " << min_memo[i] << "(index : " << min_index_memo[i] << ")" << endl;
    }*/

    //ゲームスタート
    //Halcは最小深さが最大のとこに行く
    //Sappは最大深さが最小のとこに行く
    //Halcが先だとどうなるか
    int current_node = 0, turn = 0;
    int m = 0,index = 0;
    while(child[current_node].size() > 0){
    	index = 0;
        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;
                }
            }
            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;
                }
            }
            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;
                }
            }
            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;
                }
            }
            current_node = child[current_node][index];
        }
        turn++;
    }
    cout << turn << endl;
    return 0;
}
0