제출 #615562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
615562		HamletPetrosyan	열쇠 (IOI21_keys)	C++17	9 / 100	98 ms	21612 KiB

keys

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define add push_back
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define pii pair<int, int>
#define fr first
#define sc second

const int N = 3e2 + 5;

vector<pii> g[N];
int cnt[N][N], a[N];
int color[N];

int dfs(int v, int col){
	int ret = 1;
	color[v] = col;
	for(int i = 0; i < len(g[v]); i++){
		int to = g[v][i].fr;
		if(color[to] == col) continue;
		ret += dfs(to, col);
	}
	return ret;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	vector<int> ans(len(r), 0);
	for(int i = 0; i < len(u); i++){
		g[u[i]].add({v[i], c[i]}); cnt[u[i]][c[i]]++;
		g[v[i]].add({u[i], c[i]}); cnt[v[i]][c[i]]++;
	}
	bool o = false;
	for(int i = 0; i < len(r); i++){
		if(cnt[i][r[i]] == 0){
			o = true;
			ans[i] = 1;
		}
	}
	if(o){
//		cout << "o" << endl;
		return ans;
	}
	ans.resize(len(r), 0);
	int mn = 10000009;
	for(int i = 0; i < len(r); i++){
		a[i] = dfs(i, i + 1);
		mn = min(a[i], mn);
	}
	for(int i = 0; i < len(r); i++){
		ans[i] = (a[i] == mn);
	}
	return ans;
}

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