結果

問題 No.1641 Tree Xor Query
ユーザー 👑 KazunKazun
提出日時 2021-06-25 01:13:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,823 bytes
コンパイル時間 6,007 ms
コンパイル使用メモリ 200,328 KB
実行使用メモリ 4,792 KB
最終ジャッジ日時 2023-10-17 02:21:16
合計ジャッジ時間 7,776 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Validation (Tree Xor Query)

#include <iostream>
#include "testlib.h"

using namespace std;
using ll=long long;

struct Union_Find {

	std::vector<int> parent;
	std::vector<int> rank;
	int N;

	Union_Find(int n) {
		N = n;
		parent = std::vector<int>(N, -1);
		rank = std::vector<int>(N, 0);
	}

	int find(int x) {
		if (parent[x] < 0) return x;
		return parent[x] = find(parent[x]);
	}

	int size(int x) {
		return -parent[find(x)];
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y) return;
		if (parent[x] > parent[y]) std::swap(x, y);
		parent[x] += parent[y];
		parent[y] = x;
		return;
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	int group_count() {
		int K = 0;
		for (int i = 0; i < N; i++) {
			if (parent[i] < 0) K++;
		}
		return K;
	}

	std::vector<int> members(int x) {
		std::vector<int> v(0);

		int r= find(x);
		for (int i = 0; i < N; i++) {
			if (find(i) == r) v.push_back(i);
		}
		return v;
	}
};

int main(){
    registerValidation();

    int N=inf.readInt(2,100000); inf.readSpace();
    int Q=inf.readInt(1,100000);
    inf.readEoln();

    int value_max=1024-1;

    vector<int> C=inf.readIntegers(N,0,value_max);
    inf.readEoln();

    Union_Find U(N+1);
    int a,b;
    for (int i=1; i<=N-1; i++){
        a=inf.readInt(1,N); inf.readSpace();
        b=inf.readInt(1,N);
        inf.readEoln();

        ensure(!U.same(a,b));
        U.unite(a,b);
    }

    ensure(U.group_count()==2);

    bool flag=false;
    int T,x,y;
    for (int q=1; q<=Q; q++){
        T=inf.readInt(1,2); inf.readSpace();
        x=inf.readInt(1,N); inf.readSpace();
        y=inf.readInt(0,value_max);
        inf.readEoln();

        if (T==2){
            flag=true;
            ensure(y==0);
        }
    }

    ensure(flag);
    inf.readEof();
    return 0;
}
0