제출 #827061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827061		NothingXD	열쇠 (IOI21_keys)	C++17	37 / 100	3059 ms	42488 KiB

keys

#include <bits/stdc++.h>

using namespace std;

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

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;

int n, m, r[maxn], cnt;
vector<int> ok[maxn];
bool vis[maxn];
bool mark[maxn];
vector<pii> g[maxn];
vector<int> ver[maxn];

void dfs(int v){
	cnt++;
	vis[v] = true;
	mark[r[v]] = true;
	while (!ver[r[v]].empty()){
		int u = ver[r[v]].back();
		ver[r[v]].pop_back();
		if (!vis[u]) dfs(u);
	}
	for (auto [u, x]: g[v]){
		if (!vis[u] && mark[x]){
			dfs(u);
		}
		else if (!vis[u]){
			ver[x].push_back(u);
		}
	}
}

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
	n = R.size();
	m = C.size();
	for (int i = 0; i < n; i++){
		r[i] = R[i];
	}
	for (int i = 0; i < m; i++){
		g[U[i]].push_back({V[i], C[i]});
		g[V[i]].push_back({U[i], C[i]});
	}
	int res = n+1;
	vector<int> ans;
	for (int i = 0; i < n; i++){
		memset(vis, false, sizeof vis);
		memset(mark, false, sizeof mark);
		for (int j = 0; j < n; j++) ver[j].clear();
		cnt = 0;
		dfs(i);
		if (cnt < res){
			res = cnt;
			ans.clear();
		}
		if (cnt == res) ans.push_back(i);
	}

	vector<int> output(n, 0);

	for (auto x: ans) output[x] = 1;

	return output;
}

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