Submission #1290348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290348		mariaclara	Keys (IOI21_keys)	C++17	9 / 100	319 ms	60864 KiB

keys

#include "keys.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

vi pai, tam;
set<pii> S;

int find(int x) {
    if(pai[x] == x) return x;
    return pai[x] = find(pai[x]);
}

void join(int x, int y) {
    x = find(x);
    y = find(y);

    S.erase({tam[y], y});
    tam[y] += tam[x];
    pai[x] = y;
    S.insert({tam[y], y});
}

vector<vector<pii>> edges;
vector<vi> need_key;
vi vis, keys, r, p;

int bfs(int raiz) {
    queue<int> fila;
    fila.push(raiz);

    vi change_no = {raiz}, change_key;
    int rsp = -1;

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

        if(!keys[r[x]]) {
            for(auto it : need_key[r[x]])
                vis[it] = 1, fila.push(it), change_no.pb(it);

            keys[r[x]] = 1;
            change_key.pb(r[x]);
            need_key.clear();
        }

        if(find(x) != raiz) { rsp = find(x); break; }

        for(auto [viz, nk] : edges[x]) {
            if(vis[viz]) continue;
            if(keys[nk]) vis[viz] = 1, fila.push(viz), change_no.pb(viz);
            else need_key[nk].pb(viz), change_key.pb(nk);
        }
    }

    for(auto it : change_key)
        keys[it] = 0, need_key[it].clear();

    for(auto it : change_no) {
        if(rsp == -1) p[it] = sz(change_no);
        vis[it] = 0;
    }

    return rsp;
}

vi find_reachable(vi R, vi u, vi v, vi c) {
    int n = sz(R), m = sz(c);

    pai.resize(n);
    tam.resize(n, 1);

    for(int i = 0; i < n; i++)
        pai[i] = i, S.insert({1,i});

    edges.resize(n);
    need_key.resize(n);
    vis.resize(n);
    keys.resize(n);
    p.resize(n,n+1);
    r = R;

    for(int i = 0; i < m; i++)
        edges[u[i]].pb({v[i], c[i]}), edges[v[i]].pb({u[i], c[i]});

    while(!S.empty()) {
        int x = (*S.begin()).sc, y = bfs(x);
        S.erase(S.begin());

        if(y != -1) join(x,y);
    }

    int minP = n+1;
    for(int i = 0; i < n; i++) minP = min(minP, p[i]);

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

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