제출 #1242876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242876		Ghulam_Junaid	열쇠 (IOI21_keys)	C++20	37 / 100	3098 ms	126764 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
// #include "grader.cpp"
using namespace std;

const int N = 3e5 + 10;
int n, m, ans[N], obtain[N], vis[N], mn_ans;
vector<int> key, seen[N], at_key[N], keys_seen;
vector<pair<int, int>> g[N];

void traverse(int source){
    queue<int> q;
    q.push(source);
    vis[source] = 1;
    seen[source].push_back(source);

    // cout << ":: " << source << endl;
    while (!q.empty()){
        int v = q.front();
        q.pop();
        ans[source]++;
        // cout << "visiting " << v << endl;

        int ind = lower_bound(seen[v].begin(), seen[v].end(), source) - seen[v].begin();
        if (v != source and ind < seen[v].size() and seen[v][ind] == source){
            ans[source] = ans[v] - q.size();
            break;
        }

        for (auto [k, u] : g[v]){
            if (vis[u]) continue;
            keys_seen.push_back(k);
            if (obtain[k]){
                q.push(u);
                vis[u] = 1;
                // cout << "pushingn " << u << endl;
                seen[source].push_back(u);
            }
            else
                at_key[k].push_back(u);
        }
        if (!obtain[key[v]])
            keys_seen.push_back(key[v]);
        obtain[key[v]] = 1;
        for (int x : at_key[key[v]]){
            if (!vis[x]){
                vis[x] = 1;
                // cout << "pushing " << x << endl;
                q.push(x);
                seen[source].push_back(x);
            }
        }
        at_key[key[v]].clear();

        if (ans[source] + q.size() > mn_ans)
            break;
    }
    ans[source] += q.size();

    // cout << source << " -- " << ans[source] << endl;

    mn_ans = min(mn_ans, ans[source]);
    for (int k : keys_seen){
        at_key[k].clear();
        obtain[k] = 0;
    }
    keys_seen.clear();
    for (int v : seen[source])
        vis[v] = 0;

    sort(seen[source].begin(), seen[source].end());
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	key = r, n = r.size(), m = u.size(), mn_ans = n;
    for (int i = 0; i < m; i ++){
        g[u[i]].push_back({c[i], v[i]});
        g[v[i]].push_back({c[i], u[i]});
    }

    for (int v = 0; v < n; v ++)
        traverse(v);

    vector<int> output(n);
    for (int v = 0; v < n; v ++)
        output[v] = (ans[v] == mn_ans);
	return output;
}

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