結果

問題 No.977 アリス仕掛けの摩天楼
コンテスト
ユーザー mikan
提出日時 2020-03-05 19:37:24
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,518 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 521 ms
コンパイル使用メモリ 65,368 KB
最終ジャッジ日時 2026-05-10 06:01:50
合計ジャッジ時間 1,916 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:7:12: error: 'uint64_t' was not declared in this scope
    7 |     vector<uint64_t> parent;
      |            ^~~~~~~~
main.cpp:3:1: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    2 | #include <vector>
  +++ |+#include <cstdint>
    3 | using namespace std;
main.cpp:7:20: error: template argument 1 is invalid
    7 |     vector<uint64_t> parent;
      |                    ^
main.cpp:7:20: error: template argument 2 is invalid
main.cpp:11:12: error: 'uint64_t' was not declared in this scope
   11 |     vector<uint64_t> digree;
      |            ^~~~~~~~
main.cpp:11:12: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:11:20: error: template argument 1 is invalid
   11 |     vector<uint64_t> digree;
      |                    ^
main.cpp:11:20: error: template argument 2 is invalid
main.cpp:13:23: error: expected ')' before 'N'
   13 |     UnionFind(uint64_t N) : parent(N), digree(N) {
      |              ~        ^~
      |                       )
main.cpp:20:16: error: 'uint64_t' has not been declared
   20 |     void unite(uint64_t x, uint64_t y){
      |                ^~~~~~~~
main.cpp:20:16: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:20:28: error: 'uint64_t' has not been declared
   20 |     void unite(uint64_t x, uint64_t y){
      |                            ^~~~~~~~
main.cpp:20:28: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:31:17: error: 'uint64_t' has not been declared
   31 |     bool isSame(uint64_t x, uint64_t y){
      |                 ^~~~~~~~
main.cpp:31:17: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:31:29: error: 'uint64_t' has not been declared
   31 |     bool isSame(uint64_t x, uint64_t y){

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {

    vector<uint64_t> parent;

public:

    vector<uint64_t> digree;

    UnionFind(uint64_t N) : parent(N), digree(N) {
        for(uint64_t i=0; i<N; i++){
            parent[i] = i;
            digree[i] = 0;
        }
    }

    void unite(uint64_t x, uint64_t y){
        uint64_t rx = root(x);
        uint64_t ry = root(y);
	digree[x] += 1;
	digree[y] += 1;
        if(rx == ry) {
	} else {
		parent[rx] = ry;
	}
    }

    bool isSame(uint64_t x, uint64_t y){
        uint64_t rx = root(x);
        uint64_t ry = root(y);
        return rx == ry;
    }

    int root(uint64_t x){
        if (parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }
};


int main()
{
	int N;
	cin >> N;

	UnionFind uf(N);

	for(int n=0; n<N-1; n++){
		int u, v;
		cin >> u >> v;
		uf.unite(u, v);
	}

	int root1=-1, root2=-1;
	for(int n=0; n<N; n++){
		if(root1==-1){
			root1 = uf.root(n);
		} else if(uf.root(n) == root1){
		} else if(root2 == -1){
			root2 = uf.root(n);
		} else if(uf.root(n) == root2){
		} else {
			cout << "Alice" << endl;
			return 0;
		}
	}
	if(root2 == -1){
		cout << "Bob" << endl;
		return 0;
	} else {
		if(uf.digree[root2] == 0){
			root2 = root1;
		} else if(uf.digree[root1] != 0){
			cout << "Alice" << endl;
			return 0;
		}
		for(int n=0; n<N; n++){
			if(uf.root(n) == root2 && uf.digree[n] != 2){
				cout << "Alice" << endl;
				return 0;
			} 
		}
		cout << "Bob" << endl;
		return 0;
	}
}
0