Submission #1022294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022294		edogawa_something	Keys (IOI21_keys)	C++17	37 / 100	3062 ms	41676 KiB

keys

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define pb push_back
#define F first 
#define S second 
const ll M=2e5+10;
ll res[M],root;
vector<int>r,c;
vector<pair<int,int>>edge[M];
queue<int>q;
struct DSU{
	set<ll>s[M];
	ll sz[M],pa[M];
	void init(ll x){
		for(int i=0;i<r.size();i++)
		s[i].clear(),sz[i]=1,pa[i]=i,s[i].insert(r[i]);
	}
	ll get(ll x){
		if(x==pa[x])
		return x;
		return pa[x]=get(pa[x]);
	}
	void unite(ll x,ll y){
		x=get(x),y=get(y);
		if(x==y)
		return;
		if(x==get(root)){
			for(auto it:s[y]){
				if(s[x].find(it)==s[x].end())
				q.push(it);
			}
		}
		else if(y==get(root)){
			for(auto it:s[x]){
				if(s[y].find(it)==s[y].end())
				q.push(it);
			}
		}
		if(sz[x]>sz[y])
		swap(x,y);
		for(auto it:s[x])
		s[y].insert(it);
		sz[y]+=sz[x];
		pa[x]=y;
	}
}d;
void process(ll x){
	q.push(r[x]);
	root=x;
	while(!q.empty()){
		ll x=q.front();
		q.pop();
		for(auto [u,v]:edge[x]){
			d.unite(u,v);
		}
	}	
}
std::vector<int> find_reachable(std::vector<int> rr, std::vector<int> u, std::vector<int> v, std::vector<int> cc) {
	r=rr,c=cc;
	for(int i=0;i<u.size();i++){
		edge[c[i]].pb({u[i],v[i]});
	}
	for(int i=0;i<r.size();i++){
		d.init(r.size());
		process(i);
		res[i]=d.sz[d.get(i)];
	}
	vector<int>ans(r.size());
	ll z=*min_element(res,res+r.size());
	for(int i=0;i<r.size();i++){
		ans[i]=(res[i]==z);	
	}
	return ans;
}

Compilation message (stderr)

keys.cpp: In member function 'void DSU::init(ll)':
keys.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(int i=0;i<r.size();i++)
      |               ~^~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=0;i<u.size();i++){
      |              ~^~~~~~~~~
keys.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~
keys.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~

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