Submission #534730

#	Time	Username	Problem	Language	Result	Execution time	Memory
534730		kappa	Kutije (COCI21_kutije)	C++14	35 / 70	1075 ms	9408 KiB

Main

#include <bits/stdc++.h>

using namespace std;

long long n, m, q;

struct node{
	long long parent;
	long long rank;
};

node v[200005];

long long find(long long u){
	if(u != v[u].parent){
		v[u].parent = find(v[u].parent);
	}

	return v[u].parent;
}

void merge(long long x, long long y){
	long long px = find(x);
	long long py = find(y);

	if(v[px].rank > v[py].rank){
		v[py].parent = px;
	}else{
		v[px].parent = py;
	}

	if(v[px].rank == v[py].rank){
		v[py].rank++;
	}
}

int main(){
	cin >> n >> m >> q;

	for (int i = 1; i <= n; ++i)
	{
		v[i].parent = i;
		v[i].rank = 0;
	}

	for (int i = 1; i <= m; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			int t;
			cin >> t;

			merge(t, j);
		}
	}

	while(q--){
		int l, r;
		cin >> l >> r;

		if(find(l) == find(r)){
			cout << "DA\n";
		}
		else{
			cout << "NE\n";
		}
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 35