Submission #444570

#	Time	Username	Problem	Language	Result	Execution time	Memory
444570		KLPP	Keys (IOI21_keys)	C++17	20 / 100	3072 ms	34340 KiB

keys

#include <vector>
#include<bits/stdc++.h>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
#define INF 1000000000000000LL

class DSU{
	int parent[1000000];
	int sz[1000000];
	int N;
	public:
	void init(int n){
		rep(i,0,n)parent[i]=i,sz[i]=1;
	}
	int root(int node){
		if(parent[node]==node)return node;
		parent[node]=root(parent[node]);
		return parent[node];
	}
	void merge(int a, int b){
		a=root(a);
		b=root(b);
		if(a==b)return;
		if(sz[a]<sz[b])swap(a,b);
		parent[b]=a;
		sz[a]+=sz[b];
	}
	bool same(int a, int b){
		if(root(a)==root(b))return true;
		return false;
	}
	int comp_size(int node){
		return sz[root(node)];
	}
};
DSU D;
int n,m;
vector<int> edges[1000000];
bool used[1000000];
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> ans(r.size());
	n=r.size();
	m=u.size();
	rep(i,0,m){
		edges[c[i]].push_back(i);
	}
	int minimal=n+1;
	rep(i,0,n){
		D.init(n);
		rep(j,0,n)used[j]=false;
		bool stop=false;
		while(!stop){
			stop=true;
			rep(j,0,n){
				if(D.same(i,j) && !used[r[j]]){
					used[r[j]]=true;
					stop=false;
					trav(a,edges[r[j]]){
						D.merge(u[a],v[a]);
					}
				}
			}
		}
		//cout<<D.comp_size(i)<<endl;
		if(D.comp_size(i)<minimal){
			minimal=D.comp_size(i);
			rep(j,0,n)ans[j]=0;
			ans[i]=1;
		}
		if(D.comp_size(i)==minimal){
			minimal=D.comp_size(i);
			ans[i]=1;
		}
	}
	return ans;
}

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