Submission #436508

#	Time	Username	Problem	Language	Result	Execution time	Memory
436508		CodePlatina	Keys (IOI21_keys)	C++17	67 / 100	1769 ms	1048580 KiB

keys

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

using namespace std;

//namespace A{

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

void init(void)
{
    R.clear();
    C.clear();
    for(int i = 0; i < n; ++i) gph[i].clear(), edge[i].clear(), key[i].clear();
    ran.clear();
    for(int i = 0; i < n; ++i) ord[i] = 0, rev[i + 1] = 0;
    cnt = val = 0;
}

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

    edge[x].resize(N, INF);
    key[x].resize(N, false);
    ver[x].resize(N);

    vector<pii> Q;

    key[x][R[x]] = true;
    for(int y : gph[x][R[x]]) Q.push_back({y, R[x]});

    while(Q.size())
    {
        auto [y, c] = Q.back(); Q.pop_back();
        if(!ord[y])
        {
            if(dfs(y)) return true;
            for(int i = 0; i < N; ++i)
            {
                edge[x][i] = min(edge[x][i], edge[y][i]);
                if(!key[x][i] && key[y][i])
                {
                    key[x][i] = true;
                    for(int z : gph[x][i]) Q.push_back({z, i});
                    for(int z : ver[x][i]) Q.push_back({z, i});
                }
                if(key[x][i]) for(int z : ver[y][i]) Q.push_back({z, i});
                else
                {
                    if(ver[x][i].size() < ver[y][i].size()) swap(ver[x][i], ver[y][i]);
                    for(int z : ver[y][i]) ver[x][i].push_back(z);
                }
            }
        }
        else edge[x][c] = min(edge[x][c], ord[y]);
    }

    for(int i = 0; i < N; ++i)
    {
        if(key[x][i]) ret = min(ret, edge[x][i]);
        else for(int y : gph[x][i])
        {
            if(ord[y]) edge[x][i] = min(edge[x][i], ord[y]);
            else ver[x][i].push_back(y);
        }
    }

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

    return false;
}


vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    n = r.size();
    int m = u.size();
//    init();
    N = 0;
    for(int i = 0; i < n; ++i) N = max(N, r[i]);
    for(int i = 0; i < m; ++i) N = max(N, c[i]);
    ++N;
    for(int i = 0; i < n; ++i) gph[i].resize(N);
    R = r, C = c;

    for(int i = 0; i < m; ++i)
    {
        gph[u[i]][c[i]].push_back(v[i]);
        gph[v[i]][c[i]].push_back(u[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;
}

//}
//
//namespace B{
//
//    vector<pii> gph[303030];
//
//    void init(int n)
//    {
//        for(int i = 0; i < n; ++i) gph[i].clear();
//    }
//
//    vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
//    {
//        int n = r.size();
//        int m = u.size();
//        init(n);
//        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]});
//        }
//
//        int cnt[n]{};
//        int mn = n;
//        for(int x = 0; x < n; ++x)
//        {
//            bool vst[n]{};
//            bool col[n]{};
//            vector<int> Q;
//            vector<int> ls[n];
//            Q.push_back(x);
//            while(Q.size())
//            {
//                int i = Q.back(); Q.pop_back();
//                if(vst[i]) continue;
//                vst[i] = true;
//                if(!col[r[i]])
//                {
//                    for(auto j : ls[r[i]]) Q.push_back(j);
//                    col[r[i]] = true;
//                }
//                for(auto [j, e] : gph[i])
//                {
//                    if(col[e]) Q.push_back(j);
//                    else ls[e].push_back(j);
//                }
//            }
//            for(int i = 0; i < n; ++i) if(vst[i]) ++cnt[x];
//            mn = min(mn, cnt[x]);
//        }
//
//        vector<int> ans(n);
//        for(int i = 0; i < n; ++i) if(cnt[i] == mn) ans[i] = 1;
//        return ans;
//    }
//}

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