Submission #447078

#	Time	Username	Problem	Language	Result	Execution time	Memory
447078		arnold518	Keys (IOI21_keys)	C++17	37 / 100	3053 ms	44636 KiB

keys

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, M;
int R[MAXN+10];
int ans[MAXN+10];

struct Edge
{
	int u, v, w;
};
Edge E[MAXN+10];

vector<Edge> adj[MAXN+10];

bool chk[MAXN+10], vis[MAXN+10];
vector<int> V[MAXN+10];

vector<int> find_reachable(vector<int> _R, vector<int> _U, vector<int> _V, vector<int> _C)
{
	N=_R.size(); M=_U.size();
	for(int i=1; i<=N; i++) R[i]=_R[i-1]+1;
	for(int i=1; i<=M; i++)
	{
		int u=_U[i-1]+1, v=_V[i-1]+1, w=_C[i-1]+1;
		adj[u].push_back({u, v, w});
		adj[v].push_back({v, u, w});
		E[i]={u, v, w};
	}

	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=N; j++)
		{
			vis[j]=0;
			chk[j]=0;
			V[j].clear();
		}
		queue<int> Q;
		Q.push(i);

		while(!Q.empty())
		{
			int now=Q.front(); Q.pop();
			if(vis[now]) continue;
			vis[now]=true;
			//printf("%d\n", now);

			if(chk[R[now]]==0)
			{
				for(auto it : V[R[now]])
				{
					if(vis[it]) continue;
					Q.push(it);
				}
				V[R[now]].clear();
			}
			chk[R[now]]=1;
			ans[i]++;

			for(auto nxt : adj[now])
			{
				if(vis[nxt.v]) continue;
				if(chk[nxt.w])
				{
					Q.push(nxt.v);
				}
				else
				{
					V[nxt.w].push_back(nxt.v);
				}
			}
		}
		//printf("==================\n");
	}

	int minv=ans[1];
	for(int i=1; i<=N; i++) minv=min(minv, ans[i]);
	for(int i=1; i<=N; i++) ans[i]=(minv==ans[i]);

	return vector<int>(ans+1, ans+N+1);
}

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