Submission #809735

#	Time	Username	Problem	Language	Result	Execution time	Memory
809735		qwerasdfzxcl	Keys (IOI21_keys)	C++17	100 / 100	504 ms	100596 KiB

keys

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<pair<int, int>> adj[300300], st[300300];
vector<int> nxt[300300];
int col[300300], dfn[300300], INV[300300], mn[300300], out[300300], cnt = 1;
bool visited[300300];

void dfs(int s, int pa = -1){
    dfn[s] = cnt++;
    INV[dfn[s]] = s;
    visited[s] = 1;

    mn[s] = dfn[s];
    out[s] = dfn[s];

    ///stack push
    for (auto &[c, v]:adj[s]) st[c].emplace_back(s, v);

    ///stack pop
    for (auto &[u, v]:st[col[s]]) nxt[u].push_back(v);
    st[col[s]].clear();

    ///traverse
    while(!nxt[s].empty()){
        int v = nxt[s].back(); nxt[s].pop_back();
        if (visited[v]) {mn[s] = min(mn[s], mn[v]); continue;}

        dfs(v, s);
        mn[s] = min(mn[s], mn[v]);
        out[s] = out[v];

        ///stack pop
        for (auto &[u, v]:st[col[s]]) nxt[u].push_back(v);
        st[col[s]].clear();
    }

    for (auto &[c, v]:adj[s]){
        for (int i=(int)st[c].size()-1;i>=0;i--){
            if (st[c][i].first!=s) break;
            st[c][i].first = pa;
        }
    }
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> ans(r.size());
	int n = r.size();

	///build graph
    for (int i=1;i<=n;i++){
        col[i] = r[i-1];
    }
    for (int i=0;i<(int)u.size();i++){
        adj[u[i]+1].emplace_back(c[i], v[i]+1);
        adj[v[i]+1].emplace_back(c[i], u[i]+1);
    }
	///

    for (int i=1;i<=n;i++) if (!visited[i]) dfs(i);

    int rans = 1e9;
    for (int i=1;i<=n;i++) if (mn[i]==dfn[i]) rans = min(rans, out[i] - dfn[i] + 1);
    for (int i=1;i<=n;i++) if (mn[i]==dfn[i] && out[i]-dfn[i]+1==rans){
        for (int j=dfn[i];j<=out[i];j++) ans[INV[j]-1] = 1;
    }

	return ans;
}

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