Submission #1076289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076289		jer033	Keys (IOI21_keys)	C++17	100 / 100	754 ms	63204 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 99'999'999;

vector<int> uf;

int find_one_room(int start, vector<int> (&r), vector<vector<pii>> (&edges))
{
    int key = r[start];
    for (pii x: edges[start])
    {
        if (x.second == key)
            return x.first;
    }
    return -1;
}

void init_uf(vector<int> (&directed))
{
    //cout << "yolo\n";
    int n = directed.size();
    uf = vector<int> (n, -1);
    for (int node = 0; node<n; node++)
    {
        if (uf[node]==-1)
        {
            //cout << "let's do node " << node << '\n';
            int curr = node;
            vector<int> lis;
            while (uf[curr] == -1)
            {
                uf[curr] = -2;
                lis.push_back(curr);
                curr = directed[curr];
                //cout << "damay na si " << curr << '\n';
            }
            int rep;
            if (uf[curr] == -2)
                rep = curr;
            else
                rep = uf[curr];
            
            for (int i: lis)
                uf[i] = rep;
        }
    }
    vector<int> count(n, 0);
    for (int node = 0; node<n; node++)
        count[uf[node]]--;
    
    for (int node = 0; node<n; node++)
        if (count[node]<0)
            uf[node] = count[node];
}

int fin(int x)
{
    if (uf[x]<0)
        return x;
    int y = fin(uf[x]);
    uf[x] = y;
    return y;
}

int the_thing;

void onion(int x, int y)
{
    //NOTE: Whenever this is called, it MUST be the case that we append x to y!
    x = fin(x);
    y = fin(y);
    uf[y] = uf[x]+uf[y];
    uf[x] = y;
    the_thing = y;
}

vector<int> final_answer;

int traverse(int start, vector<int> (&r), vector<vector<pii>> (&edges), bool save)
{
    map<int, bool> has_access;
    map<int, vector<int>> will_have_access;
    int n = edges.size();
    vector<bool> rooms_reached(n, 0);
    queue<int> rooms_processed;
    int ans = 1;
    rooms_reached[start] = 1;
    if (save)
        final_answer[start] = 1;
    rooms_processed.push(start);
    while (!rooms_processed.empty())
    {
        int room = rooms_processed.front();
        rooms_processed.pop();

        int new_key = r[room];
        has_access[new_key] = 1;
        for (int neigh: will_have_access[new_key])
        {
            if (rooms_reached[neigh] == 0)
            {
                rooms_reached[neigh] = 1;
                rooms_processed.push(neigh);
                ans++;

                if (fin(start) != fin(neigh))
                {
                    onion(start, neigh);
                    return -1;
                }

                if (save)
                    final_answer[neigh] = 1;
            }
        }
        will_have_access[new_key] = {};
        
        for (pii x: edges[room])
        {
            int neigh = x.first;
            int required = x.second;
            if (rooms_reached[neigh] == 0)
            {
                if (has_access[required])
                {
                    rooms_reached[neigh] = 1;
                    rooms_processed.push(neigh);
                    ans++;

                    if (fin(start) != fin(neigh))
                    {
                        onion(start, neigh);
                        return -1;
                    }
                    if (save)
                        final_answer[neigh] = 1;
                }
                else
                    will_have_access[required].push_back(neigh);
            }
        } 
    }
    return ans;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    int n = r.size();
    vector<vector<pii>> edges(n);
    int m = u.size();
    for (int i=0; i<m; i++)
    {
        int uu = u[i];
        int vv = v[i];
        int corridor = c[i];
        edges[uu].push_back({vv, corridor});
        edges[vv].push_back({uu, corridor});
    }

    bool easy = 0;
    vector<int> directed(n);
    for (int i=0; i<n; i++)
    {
        directed[i] = find_one_room(i, r, edges);
        if (directed[i] == -1)
            easy = 1;
    }

    if (easy)
    {
        vector<int> ans(n, 0);
        for (int i=0; i<n; i++)
            if (directed[i] == -1)
                ans[i] = 1;
        return ans;
    }
    //cout << "it's easy\n";

    //otherwise, we have a directed graph of n nodes and n edges
    init_uf(directed);
    priority_queue<pii> ccs;
    for (int node = 0; node<n; node++)
        if (uf[node] < 0)
            ccs.push({uf[node], node});


    //cout << "nakaabot dito\n";


    vector<int> candidate_sizes(n, INF);
    while (!ccs.empty())
    {
        //cout << "processing candidate\n";
        pii x = ccs.top();
        ccs.pop();
        x.second = fin(x.second);
        if (uf[x.second] == x.first)
        {
            int k = traverse(x.second, r, edges, 0);
            if (k<0)
            {
                int kabit = the_thing;
                kabit = fin(kabit);//precautionary measure
                if (candidate_sizes[kabit] == INF)
                {
                    ccs.push({uf[kabit], kabit});
                }
                //else{ this has already been processed earlier, and it doesn't append elsewhere }
            }
            else
            {
                candidate_sizes[x.second] = k;
            }
        }
        //else{ ignore, since that means it has been updated }
    }

    int mini = INF-1;
    for (int node = 0; node<n; node++)
        mini = min(mini, candidate_sizes[node]);
    final_answer = vector<int> (n, 0);
    for (int node = 0; node<n; node++)
        if (candidate_sizes[node] == mini)
            traverse(node, r, edges, 1);
    return final_answer;
}

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