Submission #785963

#	Time	Username	Problem	Language	Result	Execution time	Memory
785963		AdamGS	Keys (IOI21_keys)	C++17	100 / 100	1159 ms	177972 KiB

keys

#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e5+7;
int sp[LIM], cy[LIM], ile[LIM], T[LIM], nxt[LIM], n;
set<int>S[LIM], K[LIM];
set<pair<int,int>>P[LIM];
int fnds(int x) {
	if(sp[x]==x) return x;
	return sp[x]=fnds(sp[x]);
}
int fndc(int x) {
	if(cy[x]==x) return x;
	return cy[x]=fndc(cy[x]);
}
void unis(int a, int b) {
	if(fnds(a)==fnds(b)) return;
	sp[fnds(b)]=fnds(a);
}
void unic(int a, int b) {
	a=fndc(a); b=fndc(b);
	if(ile[a]<ile[b]) swap(a, b);
	ile[a]+=ile[b];
	for(auto i : S[b]) S[a].insert(i);
	for(auto i : K[b]) {
		if(K[a].find(i)==K[a].end()) {
			K[a].insert(i);
			auto it=P[a].lower_bound({i, -1});
			while(it!=P[a].end()) {
				auto p=*it;
				if(p.st!=i) break;
				S[a].insert(p.nd);
				P[a].erase(it);
				it=P[a].lower_bound({i, -1});
			}
		}
	}
	for(auto i : P[b]) if(K[a].find(i.st)!=K[a].end()) S[a].insert(i.nd); else P[a].insert(i);
	cy[b]=a;
}
vector<int>find_reachable(vector<int>r, vector<int>u, vector<int>v, vector<int>c) {
	n=r.size();
	rep(i, n) {
		T[i]=r[i];
		K[i].insert(T[i]);
		sp[i]=i;
		cy[i]=i;
		nxt[i]=-1;
		ile[i]=1;
	}
	rep(i, u.size()) {
		if(c[i]==T[u[i]]) S[u[i]].insert(v[i]);
		else P[u[i]].insert({c[i], v[i]});
		if(c[i]==T[v[i]]) S[v[i]].insert(u[i]);
		else P[v[i]].insert({c[i], u[i]});
	}
	queue<int>q;
	rep(i, n) if(S[i].size()) q.push(i);
	while(!q.empty()) {
		int p=fndc(q.front()); q.pop();
		nxt[p]=fndc(*S[p].begin());
		S[p].erase(S[p].begin());
		if(fnds(p)!=fnds(nxt[p])) {
			unis(p, nxt[p]);
			continue;
		}
		vector<int>L;
		L.pb(p);
		int x=nxt[p];
		while(fndc(x)!=fndc(p)) {
			L.pb(x);
			x=nxt[x];
		}
		rep(i, (int)L.size()-1) unic(L[i], L[i+1]);
		p=fndc(p);
		nxt[p]=-1;
		while(!S[p].empty() && fndc(*S[p].begin())==p) S[p].erase(S[p].begin());
		if(!S[p].empty()) q.push(p);
	}
	vector<int>ans(n);
	int mi=n;
	rep(i, n) if(nxt[fndc(i)]==-1) mi=min(mi, ile[fndc(i)]);
	rep(i, n) if(nxt[fndc(i)]==-1 && ile[fndc(i)]==mi) ans[i]=1;
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
keys.cpp:55:2: note: in expansion of macro 'rep'
   55 |  rep(i, u.size()) {
      |  ^~~

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33