제출 #1189902

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

keys

#include "keys.h"
#include <bits/stdc++.h>
#define maxn 300005
using namespace std;

int n, m;
int par[maxn];

int find_set(int v) {
    return par[v] < 0 ? v : par[v] = find_set(par[v]);
}

void union_set(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (par[u] < par[v]) swap(u, v);
    par[v] += par[u];
    par[u] = v;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size(); m = c.size();
    fill(par, par+n, -1);

    vector<int> p(n, 0);

    for (int i = 0; i < m; i++)
        union_set(u[i], v[i]);

    for (int i = 0; i < n; i++)
        if (r[i] == 0) p[i] = -par[find_set(i)];
        else p[i] = 1;

    vector<int> ans(n, 0);
    int d = *min_element(p.begin(), p.end());

    for (int i = 0; i < n; i++) ans[i] = (p[i] == d);
	return ans;
}

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