Submission #1307345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307345		opeleklanos	열쇠 (IOI21_keys)	C++20	37 / 100	3094 ms	24676 KiB

keys

#include <iostream>
#include <vector>
#include "keys.h"
using namespace std;

vector<vector<pair<int, int>>> adj;
vector<int> foundKeys;
vector<int> vis;
vector<int> newVis;
vector<int> key_type;
int new_nodes = 1;

void dfs(int st){
    if(!vis[st]) new_nodes++;
    newVis[st] = 1;
    vis[st] = 1;
    foundKeys[key_type[st]] = 1;
    for(auto i : adj[st]){
        if(foundKeys[i.second] && !newVis[i.first]) dfs(i.first);
    }
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
    int n = r.size();
    int m = c.size();
    key_type = r;
    vector<int> p(n, 0);
    adj.assign(n, {});
    for(int i = 0; i<m; i++){
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }
    for(int i = 0; i<n; i++){
        vis.assign(n, 0);
        new_nodes = 0;
        foundKeys.assign(n, 0);
        while(new_nodes || vis[i] == 0){
            new_nodes = 0;
            newVis.assign(n, 0);
            dfs(i);
        }
        for(int j = 0; j<n; j++) if(vis[j]) p[i]++;
    }
    int mn = n;
    for(int i = 0; i<n; i++) mn = min(mn, p[i]);
    for(int i = 0; i<n; i++) p[i] = (p[i] == mn)?1:0;
    return p;
}

// int main(void){
//     freopen("input.txt", "r", stdin);
//     int n1, m1;
//     cin>>n1>>m1;
//     vector<int> r1(n1);
//     vector<int> u1(n1);
//     vector<int> v1(n1);
//     vector<int> c1(n1);
//     for(int i = 0; i<n1; i++) cin>>r1[i];
//     for(int i = 0; i<m1; i++){
//         cin>>u1[i]>>v1[i]>>c1[i];
//     }
//     vector<int> ans = find_reachable(r1, u1, v1, c1);
//     for(auto i : ans) cout<<i<<endl;
// }

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