Submission #1058830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058830		LittleOrange	Keys (IOI21_keys)	C++17	0 / 100	1 ms	348 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 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(), 1);
	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;
	}
	return ans;
}

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