Submission #435458

#	Time	Username	Problem	Language	Result	Execution time	Memory
435458		Muhammetali	Keys (IOI21_keys)	C++17	9 / 100	2578 ms	31344 KiB

keys

#include <bits/stdc++.h>
#define mp make_pair
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) x.begin(),x.end()
#define all_r(x) x.rbegin(),x.rend()
#define clr(a) memset((a),0,sizeof(a))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef pair<ll,ll> pl;
typedef vector<ll> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef priority_queue<ll,vl,greater<ll>> pqg;
int R[300000];
vpi adj[300000];
set<int>st,key;
void find(int k,int ind){
	st.ins(k);
	key.ins(R[k]);
	for(int i:st){
		for(auto it:adj[i]){
			if(st.count(it.ff)==1 || key.count(it.ss)==0)continue;
			find(it.ff,ind);
			return;
		}
	}
}
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
	int n=sz(r);
	int m=sz(u);
	vector<int> ans(n,1);
	for(int i=0;i<n;i++)R[i]=r[i];
	for(int i=0;i<m;i++){
		adj[u[i]].pb({v[i],c[i]});
		adj[v[i]].pb({u[i],c[i]});
	}
	int res=INT_MAX;
	for(int i=0;i<n;i++){
		st.clear();
		key.clear();
		st.ins(i);
		key.ins(r[i]);
		bool vis=0;
		for(auto it:adj[i]){
			if(ans[it.ff]!=1 && r[i]==it.ss){
				vis=1;
				ans[i]=ans[it.ff];
				break;
			}
		}
		if(!vis){
			find(i,i);
			ans[i]=sz(st);
		}
		if(res>ans[i])res=ans[i];
	}
	for(int i=0;i<n;i++){
		if(ans[i]==res)ans[i]=1;
		else ans[i]=0;
	}
	return ans;
}

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