Submission #2514748


Source Code Expand

#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<queue>
#include<cassert>
#include<tuple>
#include<set>
#include<map>
#include<list>
#include<bitset>

#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define DWN(a)  (a).begin(),(a).end(), greater<int>()
#define rep(i, m) for (int i = 0; i < m; i++)
#define REP(i, n, m) for (int i = n; i < m; i++)

#define mod 1000000007

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
const int INF = (int)1e9;


struct UnionFind {
	vector<int> rank, par;

	void set(int n) {
		rank.resize(n, 0);
		par.resize(n, 0);
		rep(i, n) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x) {
		if (x != par[x]) par[x] = find(par[x]);
		return par[x];
	}

	void unite(int a, int b) {
		int x = find(a);
		int y = find(b);
		if (rank[x] > rank[y]) {
			par[y] = x;
		}
		else {
			par[x] = y;
			if (rank[x] == rank[y]) {
				rank[y]++;
			}
		}
	}

	bool same(int a, int b) {
		return find(a) == find(b);
	}
};

int main() {
	int n, q;
	cin >> n >> q;
	UnionFind uf;
	uf.set(2 * n);
	for (int i = 0; i < q; i++) {
		int w, x, y, z;
		cin >> w >> x >> y >> z;
		x--; y--;
		if (w == 1) {
			if (z % 2 == 0) {
				uf.unite(x, y);
				uf.unite(x + n, y + n);
			}
			else {
				uf.unite(x, y + n);
				uf.unite(x + n, y);
			}
		}
		if(w == 2) {
			if (uf.same(x, y)) {
				cout << "YES" << endl;
			}
			else {
				cout << "NO" << endl;
			}
		}
	}
	return 0;
}

Submission Info

Submission Time
Task D - 偶数メートル
User tako_39
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1718 Byte
Status AC
Exec Time 180 ms
Memory 1920 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 32
AC × 62
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 6 ms 256 KB
subtask1_04.txt AC 4 ms 256 KB
subtask1_05.txt AC 4 ms 256 KB
subtask1_06.txt AC 4 ms 256 KB
subtask1_07.txt AC 4 ms 256 KB
subtask1_08.txt AC 5 ms 256 KB
subtask1_09.txt AC 6 ms 256 KB
subtask1_10.txt AC 6 ms 256 KB
subtask1_11.txt AC 6 ms 256 KB
subtask1_12.txt AC 6 ms 256 KB
subtask1_13.txt AC 6 ms 256 KB
subtask1_14.txt AC 6 ms 256 KB
subtask1_15.txt AC 6 ms 256 KB
subtask1_16.txt AC 6 ms 256 KB
subtask1_17.txt AC 6 ms 256 KB
subtask1_18.txt AC 6 ms 256 KB
subtask1_19.txt AC 6 ms 256 KB
subtask1_20.txt AC 6 ms 256 KB
subtask1_21.txt AC 6 ms 256 KB
subtask1_22.txt AC 6 ms 256 KB
subtask1_23.txt AC 6 ms 256 KB
subtask1_24.txt AC 6 ms 256 KB
subtask1_25.txt AC 6 ms 256 KB
subtask1_26.txt AC 6 ms 256 KB
subtask1_27.txt AC 6 ms 256 KB
subtask1_28.txt AC 6 ms 256 KB
subtask1_29.txt AC 6 ms 256 KB
subtask2_01.txt AC 63 ms 640 KB
subtask2_02.txt AC 149 ms 1792 KB
subtask2_03.txt AC 11 ms 768 KB
subtask2_04.txt AC 145 ms 1280 KB
subtask2_05.txt AC 65 ms 1792 KB
subtask2_06.txt AC 70 ms 1408 KB
subtask2_07.txt AC 138 ms 1920 KB
subtask2_08.txt AC 156 ms 1536 KB
subtask2_09.txt AC 95 ms 896 KB
subtask2_10.txt AC 179 ms 1920 KB
subtask2_11.txt AC 178 ms 1920 KB
subtask2_12.txt AC 178 ms 1920 KB
subtask2_13.txt AC 179 ms 1920 KB
subtask2_14.txt AC 179 ms 1920 KB
subtask2_15.txt AC 177 ms 1920 KB
subtask2_16.txt AC 178 ms 1920 KB
subtask2_17.txt AC 178 ms 1920 KB
subtask2_18.txt AC 180 ms 1920 KB
subtask2_19.txt AC 178 ms 1920 KB
subtask2_20.txt AC 180 ms 1920 KB
subtask2_21.txt AC 106 ms 1792 KB
subtask2_22.txt AC 106 ms 1792 KB
subtask2_23.txt AC 106 ms 1792 KB
subtask2_24.txt AC 105 ms 1792 KB
subtask2_25.txt AC 106 ms 1792 KB
subtask2_26.txt AC 107 ms 1792 KB
subtask2_27.txt AC 108 ms 1792 KB
subtask2_28.txt AC 106 ms 1792 KB
subtask2_29.txt AC 106 ms 1792 KB
subtask2_30.txt AC 172 ms 1152 KB