Submission #1015321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015321		vako_p	Kutije (COCI21_kutije)	C++14	70 / 70	107 ms	9564 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e3 + 5;
ll n,p[mxN],m,q;
bool vis[mxN];

struct ds{
	vector<ll> par,rank;
	
	void init(){
		par.resize(mxN);
		rank.assign(mxN, 0LL);
		for(int i = 0; i <= n; i++) par[i] = i;
	}	
	
	ll find(ll a){
		if(par[a] == a) return a;
		par[a] = find(par[a]);
		return par[a];
	}
	
	void merge(ll a, ll b){
		a = find(a);
		b = find(b);
		if(a == b) return;
		par[b] = a;
		rank[a] += (rank[a] == rank[b]);
	}
};

ds s;

void dfs(ll at){
	if(vis[at]) return;
	vis[at] = true;
	s.merge(at, p[at]);
	dfs(p[at]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> q;
	s.init();
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			cin >> p[j];
			vis[j] = false;
		}
		for(int j = 1; j <= n; j++){
			dfs(j); 
		}
	}
	while(q--){
		ll a, b;
		cin >> a >> b;
		if(s.find(a) == s.find(b)) cout << "DA" << '\n';
		else cout << "NE" << '\n';
	}	
}

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