Submission #1058875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058875		LittleOrange	Keys (IOI21_keys)	C++17	20 / 100	372 ms	79916 KiB

keys

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct dsu{
    ll n;
    vector<ll> p;
    dsu(ll N):n(N),p(N,-1){}
    ll g(ll i){
        return p[i]<0?i:p[i]=g(p[i]);
    }
	bool e(ll a, ll b){
		return g(a)==g(b);
	}
    bool m(ll a, ll b){
        a = g(a);
        b = g(b);
        if(a==b) return false;
        if(p[a]>p[b]) swap(a,b);
        p[a]+=p[b];
        p[b]=a;
        return true;
    }
	ll sz(ll i){
		return -p[g(i)];
	}
};

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	ll n = r.size();
	ll m = u.size();
	std::vector<int> ans(r.size(), 0);
	/*ll task1 = 1;
	for(ll i : c) if(i) task1 = 0;
	if (task1){
		ll zc = 0;
		for(ll i : r){
			zc += i==0;
		}
		if(zc!=n){
			vector<ll> ret(n,0);
			for(ll i = 0;i<n;i++) ret[i] = r[i]!=0;
			return ret;
		}
		dsu d(n);
		for(ll i = 0;i<m;i++) d.m(u[i],v[i]);
		ll mi = n;
		for(ll i = 0;i<n;i++) mi = min(mi,d.sz(i));
		vector<ll> ret(n,0);
		for(ll i = 0;i<n;i++) ret[i] = d.sz(i)==mi;
		return ret;
	}*/
	vector<set<ll>> con(n);
	for(ll i = 0;i<m;i++){
		if (r[u[i]]==c[i]) con[u[i]].insert(v[i]);
		if (r[v[i]]==c[i]) con[v[i]].insert(u[i]);
	}
	ll easy = 0;
	for(auto &o : con) if(o.empty()) easy = 1;
	if(easy){
		for(ll i = 0;i<n;i++) ans[i] = con[i].size()==0;
		return ans;
	}
	vector<ll> bad(n,0),ins(n,0),st;
	dsu d(n);
	function<void(ll)> dfs;
	dfs = [&](ll i){
		if(bad[i]) return;
		ins[i] = 1;
		st.push_back(i);
		for(ll j : con[i]){
			if (ins[j]){
				for(ll x = st.size()-1;st[x]!=j;x--){
					d.m(st[x],st[x-1]);
				}
			}else{
				dfs(j);
			}
		}
		ins[i] = 0;
		st.pop_back();
		bad[i] = 1;
	};
	ll run = 1;
	while(run){
		run = 0;
		for(ll i = 0;i<n;i++) dfs(i);
		vector<set<ll>> ks(n);
		for(ll i = 0;i<n;i++) ks[d.g(i)].insert(r[i]);
		for(ll i = 0;i<m;i++){
			if (ks[d.g(u[i])].count(c[i])) run|=con[u[i]].insert(v[i]).second;
			if (ks[d.g(v[i])].count(c[i])) run|=con[v[i]].insert(u[i]).second;
		}
	}
	vector<ll> ok(n,1);
	for(ll i = 0;i<n;i++){
		for(ll j : con[i]){
			if (!d.e(i,j)) ok[d.g(i)] = 0;
		}
	}
	ll mi = n;
	for(ll i = 0;i<n;i++){
		if (ok[d.g(i)]) mi = min(mi,d.sz(i));
	}
	for(ll i = 0;i<n;i++) ans[i] = ok[d.g(i)]&&d.sz(i)==mi;
	return ans;
}

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