Submission #545567

#	Time	Username	Problem	Language	Result	Execution time	Memory
545567		qwerasdfzxcl	Keys (IOI21_keys)	C++17	9 / 100	189 ms	39560 KiB

keys

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<pair<int, int>> adj[300300];
int num[300300], INV[300300], L[300300], R[300300], dep[300300], mdep[300300], mnum[300300], col[300300], cnt = 1, rdep[300300];
bool on[300300], leaf[300300];

bool comp(int x, int y){
    return dep[x] < dep[y];
}

void dfs(int s, int pa = -1){
    //int org = s;
    num[s] = cnt; ///renumbering
    INV[cnt] = s;
    s = num[s];
    cnt++;

    if (pa!=-1) dep[s] = dep[pa] + 1;
    L[s] = s, R[s] = s;
    mdep[s] = s, mnum[s] = s;
    on[s] = 1, leaf[s] = 1;

    for (auto &[v, c]:adj[INV[s]]) if (col[INV[s]] == c){
        if (!num[v]){
            leaf[s] = 0;

            dfs(v, s);
            R[s] = R[num[v]];
            mdep[s] = min(mdep[s], mdep[num[v]], comp);
            mnum[s] = min(mnum[s], mnum[num[v]]);
        }
        else if (on[num[v]]){
            //printf("YES %d -> %d, c = %d\n", org, v, c);
            mdep[s] = min(mdep[s], num[v], comp);
        }
        else if (num[v]<s){
            //printf("YES\n");
            mnum[s] = min(mnum[s], num[v]);
        }
    }

    //printf(" %d -> %d: %d %d\n", org, s, L[s], R[s]);

    on[s] = 0;
}

bool valid(int s){
    return mdep[s]==s && mnum[s]==s;
}

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(v[i]+1, c[i]);
        adj[v[i]+1].emplace_back(u[i]+1, c[i]);
    }
	///

    for (int i=1;i<=n;i++) if (!num[i]){
        dfs(i);
        //printf("%d -> %d: %d %d\n", i, num[i], L[i], R[i]);
    }

    for (int i=1;i<=n;i++){
        if (mdep[i]==i) rdep[i] = i;
        else rdep[i] = rdep[mdep[i]];

        //printf("%d: %d %d\n", i, mdep[i], rdep[i]);
    }

    int mx = -1, cans = 1e9;
    for (int i=1;i<=n;i++) if (leaf[i] && i>mx){
        int Rt = rdep[i];
        if (!valid(Rt)) continue;

        cans = min(cans, R[Rt]-L[Rt]+1);
        mx = R[Rt];
    }

    mx = -1;
    for (int i=1;i<=n;i++) if (leaf[i] && i>mx){
        int Rt = rdep[i];
        if (!valid(Rt) || cans<R[Rt]-L[Rt]+1) continue;

        //printf("%d: %d %d %d\n", i, L[Rt], R[Rt], cans);

        for (int j=L[Rt];j<=R[Rt];j++) ans[INV[j]-1] = 1;
        mx = R[Rt];
    }

	return ans;
}

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