Submission #836672

#	Time	Username	Problem	Language	Result	Execution time	Memory
836672		FulopMate	Keys (IOI21_keys)	C++17	37 / 100	3039 ms	24460 KiB

keys

#include <bits/stdc++.h>

using namespace std;

#define ll long long

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {

    int n = r.size(), m = u.size();
    vector<vector<pair<int, int>>> g(n);
    for(int i = 0; i < m; i++){
        g[u[i]].push_back({v[i], c[i]});
        g[v[i]].push_back({u[i], c[i]});
    }

    vector<int> reachable(n, 0);

    for(int i = 0; i < n; i++){

        vector<bool> unlocked(n, 0), visited(n, 0);
        unlocked[r[i]] = 1;
        visited[i] = true;
        vector<vector<int>> kesobb(n);
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            int c = q.front(); q.pop();
            if(!unlocked[r[c]]){
                unlocked[r[c]] = true;
                for(int j : kesobb[r[c]]){
                    if(!visited[j]){
                        q.push(j);
                        visited[j] = true;
                    }
                }
            }
            for(auto& j : g[c]){
                if(unlocked[j.second]){
                    if(!visited[j.first]){
                        q.push(j.first);
                        visited[j.first] = true;
                    }
                } else {
                    kesobb[j.second].push_back(j.first);
                }
            }
        }

        for(int j : visited){
            reachable[i]+=j;
        }

    }

    int mn = 1e9;
    for(int i = 0; i < n; i++)mn = min(mn, reachable[i]);
    vector<int> ans(n, 0);
    for(int i = 0; i < n; i++)ans[i] = reachable[i] == mn;

	return ans;
}


// n * n * m


// int main() {
//     int n, m;
//     assert(2 == scanf("%d%d", &n, &m));
//     vector<int> r(n), u(m), v(m), c(m);
//     for(int i=0; i<n; i++) {
//         assert(1 == scanf("%d", &r[i]));
//     }
//     for(int i=0; i<m; i++) {
//         assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
//     }
//     fclose(stdin);

//     vector<int> ans = find_reachable(r, u, v, c);

//     for (int i = 0; i < (int) ans.size(); ++i) {
//         if(i) putchar(' ');
//         putchar(ans[i]+'0');
//     }
//     printf("\n");
//     return 0;
// }

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