Submission #848273

#	Time	Username	Problem	Language	Result	Execution time	Memory
848273		grossly_overconfident	Keys (IOI21_keys)	C++17	37 / 100	1249 ms	2097152 KiB

keys

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

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
    int n = r.size();
    int m = u.size();
    vector<vector<int>> adj(n);
    vector<vector<vector<int>>> lock(n, vector<vector<int>>(n));
    for (int i = 0; i < m; ++i){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
        lock[u[i]][v[i]].push_back(c[i]);
        lock[v[i]][u[i]].push_back(c[i]);
    }
    vector<int> out(n);
    for (int i = 0; i < n; ++i){
        vector<bool> visited(n, false);
        int count = 0;
        set<int> obtained = {-1};
        deque<pair<int, int>> dq;
        dq.push_back({i, -1});
        while (!dq.empty()){
            auto h = dq.front();
            dq.pop_front();
            if (visited[h.first]){
                continue;
            }
            if (obtained.find(h.second) == obtained.end()){
                continue;
            }
            visited[h.first] = true;
            obtained.insert(r[h.first]);
            count += 1;
            for (auto k : adj[h.first]){
                for (auto e : lock[h.first][k]){
                    if (obtained.find(e) != obtained.end()){
                        dq.push_front({k, e});
                    }
                    else{
                        dq.push_back({k, e});
                    }
                }
            }
        }
        out[i] = count;
    }
    int worst = out[0];
    for (int i = 0; i < n; ++i){
        worst = min(worst, out[i]);
    }
    for (int i = 0; i < n; ++i){
        out[i] = out[i] == worst;
    }
    return out;
}
signed tester(){
    vector<int> out = find_reachable({0, 1, 1, 2, 2, 1, 2},
                                    {0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
                                    {1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
                                    {0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
    for (auto k : out){
        cout << k << " ";
    }
}

Compilation message (stderr)

keys.cpp: In function 'int tester()':
keys.cpp:64:1: warning: no return statement in function returning non-void [-Wreturn-type]
   64 | }
      | ^

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