제출 #481493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
481493		8e7	Keys (IOI21_keys)	C++17	37 / 100	3084 ms	35152 KiB

keys

//Challenge: Accepted
#include "keys.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
	cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
	while (l!= r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int col[maxn], num[maxn];
bool cur[maxn], vis[maxn];
vector<pii> adj[maxn];
vector<int> cand[maxn];
int tot = 0;
void dfs(int n) {
	tot++;
	vis[n] = 1;
	cur[col[n]] = 1;
	for (auto v:adj[n]) {
		if (!vis[v.ff]) {
			if (cur[v.ss]) dfs(v.ff);
			else cand[v.ss].push_back(v.ff);
		}
	}
	for (int v:cand[col[n]]) {
		if (!vis[v]) dfs(v);
	}
	cand[col[n]].clear();
}
vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = r.size(), m = c.size();
	for (int i = 0;i < n;i++) col[i] = r[i];
	vector<int> ans(n, 0);
	for (int i = 0;i < m;i++) {
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
	}
	int best = n + 1;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) cand[j].clear(), cur[j] = vis[j] = 0;
		tot = 0;
		dfs(i);
		num[i] = tot, best = min(best, tot);	
	}
	for (int i = 0;i < n;i++) {
		if (num[i] == best) ans[i] = 1;
	}
	return ans;
}

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