Submission #799909

#	Time	Username	Problem	Language	Result	Execution time	Memory
799909		TheSahib	Keys (IOI21_keys)	C++17	37 / 100	245 ms	20892 KiB

keys

#include <vector>
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int oo = 1e9 + 9;
const int MAX = 2005;

struct edge{
    int v, u, c;
};

int n, m;
vector<edge> g[MAX];
int keys[MAX];

bool visited[MAX];
bool K[MAX];
int calc(int start){
    memset(visited, 0, sizeof(visited));
    memset(K, 0, sizeof(K));

    int ans = 0;

    set<pii> st;
    queue<int> q;
    q.push(start);
    
    while(!q.empty()){
        ans += 1;
        
        int node = q.front();
        int k = keys[node];
        
        visited[node] = 1;
        K[k] = 1;


        q.pop();
        for(auto e:g[node]){
            if(visited[e.u]) continue;
            if(K[e.c]){
                q.push(e.u);
                visited[e.u] = 1;
                continue;
            }
            st.insert({e.c, e.u});
        }
        auto b = st.lower_bound({k, 0});
        auto e = st.upper_bound({k, oo});
        for(auto itr = b; itr != e; ++itr){
            int a = itr->second;
            if(visited[a]) continue;
            q.push(a);
            visited[a] = 1;
        }
        if(b == e) continue;
        st.erase(b, e);
    }
    return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size();
    m = u.size();
    for (int i = 0; i < n; i++)
    {
        keys[i] = r[i];
    }
    for (int i = 0; i < m; i++)
    {
        g[u[i]].push_back({u[i], v[i], c[i]});
        g[v[i]].push_back({v[i], u[i], c[i]});
    }
    vector<int> ans(n, 0);
    vector<vector<int>> cnt(n + 1);
    for (int i = 0; i < n; i++)
    {
        cnt[calc(i)].push_back(i);
    }
    for (int i = 0; i <= n; i++)
    {
        if(cnt[i].empty()) continue;
        for(int a:cnt[i]){
            ans[a] = 1;
        }
        break;
    }
    return ans;
}

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