제출 #817051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817051		vjudge1	Keys (IOI21_keys)	C++17	37 / 100	209 ms	22856 KiB

keys

#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N = 5000;
vector<pii> G[N];
vector<pii> NG[N];
vector<int> find_reachable(vector <int> r, vector <int> u, vector <int> v, vector <int> c) {
	int n = (int)r.size();
	vi ans(n, 1), C(n, 0);
	for (int i = 0; i < (int)u.size(); i++) {
		G[u[i]].pb({v[i], c[i]});
		G[v[i]].pb({u[i], c[i]});
	}
	for (int i = 0; i < n; i++) {
		set <pii> wait;
		vector<bool> vis(n, 0);
		vector<bool> have(n, 0);
		queue <int> q;
		q.push(i);
		while (!q.empty()) {
			C[i]++;
			int at = q.front();
			q.pop();
			have[r[at]] = 1;
			for (auto next : G[at]) if (!vis[next.first]) {
				if (have[next.second]) {
					vis[next.first] = 1;
					q.push(next.first);
				} else {
					wait.insert({next.second, next.first});
				}
			}
			while (1) {
				auto it = wait.lower_bound(make_pair(r[at], -1));
				if (it != wait.end() && (*it).first == r[at]) {
					if (!vis[(*it).second]) {
						vis[(*it).second] = 1;
						q.push((*it).second);
					}
					wait.erase(it);
				} else {
					break;
				}
			}
		}
	}
 
	int mn = *min_element(C.begin(), C.end());
	for (int i = 0; i < n; i++) {
		if(C[i] == mn) ans[i] = 1;
		else ans[i] = 0;
	}
	return ans;
}

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