Submission #742924

#	Time	Username	Problem	Language	Result	Execution time	Memory
742924		Mauve	Keys (IOI21_keys)	C++17	37 / 100	254 ms	20804 KiB

keys

#include<bits/stdc++.h>
using namespace std; 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 2010; vector <pii> edge[maxn];int cnt[maxn];int mn = mod;vector <int> ans;
int f[maxn];int R[maxn];
vector <int> v[maxn];
bool vis[maxn];int n,m; 
int getf(int x) {
	if (f[x]==x) return x;	
	else return f[x] = getf(f[x]);
} 
int solve(int node) {
		memset(vis,false,sizeof(vis));
			rep(i,0,n) {
				f[i] = i;		
				while (!v[i].empty()) v[i].pop_back();
				v[i].pb(i);
			}	
			vector <int> tmp;	
			tmp.pb(R[node]);	
			vis[R[node]]=true;	
			while (!tmp.empty()) {
				int cur = tmp.back();	
					tmp.pop_back();	
						for (auto it:edge[cur]) {	
							int uu = getf(it.fi),vv=getf(it.se);	
							if (uu==vv) continue;		
							if (vv==getf(node)) swap(uu,vv);	
							if (uu==getf(node)) {		
							for (int x:v[vv]) {	
							if (!vis[R[x]]) vis[R[x]]=true,tmp.pb(R[x]);
							}
							}		
							if (SZ(v[uu])<SZ(v[vv])) swap(uu,vv);		
							while (!v[vv].empty()) v[uu].pb(v[vv].back()),v[vv].pop_back();	
							f[vv]=uu;	
						}
			}
	return SZ(v[getf(node)]);
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
		n = SZ(r);
		rep(i,0,SZ(r)) R[i]= r[i];	
		rep(i,0,SZ(u)) edge[c[i]].pb({u[i],v[i]});	
		rep(i,0,SZ(r)) cnt[i] = solve(i),mn = min(mn,cnt[i]);	
		rep(i,0,SZ(r)) {		
			if (cnt[i]==mn) ans.pb(1);
			else ans.pb(0);	
		}
		return ans;
	}

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