Submission #440588

#	Time	Username	Problem	Language	Result	Execution time	Memory
440588		BaraaArmoush	Keys (IOI21_keys)	C++17	37 / 100	108 ms	19056 KiB

keys

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2020;

int n;
int R[N];
bool vis1[N];
bool vis2[N];
bool have[N];
queue<int> q1;
queue<int> q2[N];
vector<pii> adj[N];

void clear(queue<int>& q) {
    while (!q.empty()) {
        q.pop();
    }
}

int count(int x) {
    memset(vis1, false, sizeof(vis1));
    memset(vis2, false, sizeof(vis2));
    memset(have, false, sizeof(have));

    clear(q1);
    for (int i = 0; i < n; i++) {
        clear(q2[i]);
    }

    q1.push(x);

    int answer = 0;

    while (!q1.empty()) {
        int x = q1.front();
        q1.pop();

        if (vis1[x]) {
            continue;
        }

        answer++;
        vis1[x] = true;

        if (!have[R[x]]) {
            have[R[x]] = true;

            while (!q2[R[x]].empty()) {
                int y = q2[R[x]].front();
                q2[R[x]].pop();
                q1.push(y);
            }
        }

        for (const pii& p : adj[x]) {
            int y = p.first, w = p.second;

            if (!vis1[y]) {
                if (have[w]) {
                    q1.push(y);
                } else {
                    q2[w].push(y);
                }
            }
        }
    }

    return answer;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size();
    int m = u.size();

    for (int i = 0; i < n; i++) {
        R[i] = r[i];
    }

    for (int j = 0; j < m; j++) {
        adj[u[j]].emplace_back(v[j], c[j]);
        adj[v[j]].emplace_back(u[j], c[j]);
    }

    vector<int> answer(n);

    for (int i = 0; i < n; i++) {
        answer[i] = count(i);
    }

    int minimum = *min_element(answer.begin(), answer.end());

    for (int& x : answer) {
        x = (x == minimum);
    }

    return answer;
}

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