Submission #805124

#	Time	Username	Problem	Language	Result	Execution time	Memory
805124		eltu0815	Keys (IOI21_keys)	C++17	100 / 100	1165 ms	62192 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int n, m, cnt;
int p[300005], vis[300005], used[300005], key[300005];
int parent[300005];
vector<int> vec[300005];
vector<pii> graph[300005];

int Find(int x) {
    if(parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}

int bfs(int i) {
    queue<int> q;
    vector<int> st1, st2;
    q.push(i);
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        if(Find(i) != Find(cur)) {
            for(auto v : st1) used[key[v]] = 0;
            for(auto v : st2) vec[v].clear();
            return cur;
        }
        
        if(vis[cur]) continue;
        vis[cur] = 1;
        
        st1.push_back(cur);
        if(!used[key[cur]]) {
            used[key[cur]] = 1;
            for(auto v : vec[key[cur]]) q.push(v);
        }
        for(auto v : graph[cur]) {
            if(used[v.second]) q.push(v.first);
            else st2.push_back(v.second), vec[v.second].push_back(v.first);
        }
    }
    for(auto v : st1) p[v] = st1.size(), used[key[v]] = 0;
    for(auto v : st2) vec[v].clear();
    return -1;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n = r.size(), m = u.size();	
	for(int i = 0; i < n; ++i) key[i] = r[i], parent[i] = i, p[i] = (int)(1e9);
	for(int i = 0; i < m; ++i) {
        graph[u[i]].push_back({v[i], c[i]});
        graph[v[i]].push_back({u[i], c[i]});
	}
	
	int flag = 1;
	while(flag) {
        flag = 0; ++cnt;
        vector<pii> lst;
        for(int i = 0; i < n; ++i) vis[i] = 0;
        for(int i = 0; i < n; ++i) {
            if(Find(i) != i) continue;
            int ret = bfs(i);
            if(ret != -1) lst.push_back({ret, i}), flag = 1;
        }
        for(auto v : lst) parent[Find(v.second)] = Find(v.first);
	}
    
    vector<int> ans;
    int mn = *min_element(p, p + n);
    for(int i = 0; i < n; ++i) ans.push_back(p[i] == mn);
	return ans;
}

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