Submission #836618

#	Time	Username	Problem	Language	Result	Execution time	Memory
836618		FulopMate	Keys (IOI21_keys)	C++17	20 / 100	3067 ms	8428 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<int> reachable(n, 0);

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

        reachable[i] = 1;
        vector<bool> unlocked(n, 0), visited(n, 0);
        unlocked[r[i]] = 1;
        visited[i] = true;
        bool b = true;
        while(b){
            b = false;
            for(int j = 0; j < m; j++){
                if((visited[u[j]] ^ visited[v[j]]) && unlocked[c[j]]){
                    b = true;
                    reachable[i]++;
                    visited[u[j]] = visited[v[j]] = true;
                    unlocked[r[u[j]]] = unlocked[r[v[j]]] = true;
                }
            }
        }

    }

    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: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33