Submission #436544

#	Time	Username	Problem	Language	Result	Execution time	Memory
436544		CodePlatina	Keys (IOI21_keys)	C++17	100 / 100	1462 ms	198976 KiB

keys

#include <vector>
#include <algorithm>
#include <tuple>
#include <set>
#include <map>
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ff first
#define ss second

using namespace std;

const int INF = (int)1e9 + 7;
vector<int> R, C;
vector<pii> gph[303030];
map<int, int> edge[303030];
map<int, vector<int>> ver[303030];
set<int> key[303030];
vector<pii> ran;
int ord[303030];
int rev[303030];
int cnt = 0;
int val = 0;

int dfs(int x)
{
    int ret = ord[x] = ++cnt;
    rev[cnt] = x;

    vector<int> Q;
    for(auto [y, c] : gph[x])
    {
        if(c == R[x]) Q.push_back(y);
        else if(!ord[y]) ver[x][c].push_back(y);
        else
        {
            if(edge[x].count(c)) edge[x][c] = min(edge[x][c], ord[y]);
            else edge[x][c] = ord[y];
        }
    }
    key[x].insert(R[x]);

    while(Q.size())
    {
        int y = Q.back(); Q.pop_back();
        if(!ord[y])
        {
            int t = dfs(y);
            if(t == -1) return -1;
            ret = min(ret, t);

            if(ver[x].size() + edge[x].size() + key[x].size() < ver[y].size() + edge[y].size() + key[x].size())
            {
                swap(ver[x], ver[y]);
                swap(edge[x], edge[y]);
                swap(key[x], key[y]);
            }

            for(int c : key[y])
            {
                if(ver[x].count(c))
                {
                    for(int z : ver[x][c]) Q.push_back(z);
                    ver[x].erase(c);
                }
                if(edge[x].count(c))
                {
                    ret = min(ret, edge[x][c]);
                    ver[x].erase(c);
                }
                key[x].insert(c);
            }

            for(auto [c, val] : edge[y])
            {
                if(key[x].count(c)) ret = min(ret, val);
                else
                {
                    if(edge[x].count(c)) edge[x][c] = min(edge[x][c], val);
                    else edge[x][c] = val;
                }
            }

            for(auto &[c, v] : ver[y])
            {
                if(key[x].count(c)) for(auto z : v) Q.push_back(z);
                else
                {
                    if(ver[x].count(c))
                    {
                        if(ver[x][c].size() < v.size()) swap(ver[x][c], v);
                        for(auto z : v) ver[x][c].push_back(z);
                    }
                    else ver[x][c] = v;
                }
            }
        }
        else ret = min(ret, ord[y]);
    }

    if(ret < val) { val = ord[x] + 1; return -1; }
    if(ret >= ord[x])
    {
        ran.push_back({ord[x], cnt});
        val = cnt + 1;
        return -1;
    }

    return ret;
}

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

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

    for(int i = 0; i < n; ++i) if(!ord[i]) dfs(i);

    int mn = INF;
    for(auto [x, y] : ran) mn = min(mn, y - x);
    vector<int> ans(n);
    for(auto [x, y] : ran) if(mn == y - x)
    {
        for(int i = x; i <= y; ++i)
            ans[rev[i]] = 1;
    }
    return ans;
}

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