제출 #805610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805610		raysh07	열쇠 (IOI21_keys)	C++17	0 / 100	6 ms	14292 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e9

int n, m;
const int N = 3e5 + 69;
vector <pair<int, int>> adj[N];
vector <int> pend[N];
bool have[N], vis[N]; //do i have this colour? 
int cnt[N];

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 < m; i++){
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }
    
    int mn = INF;
    
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            have[j] = false;
            pend[j].clear();
        }
        
        queue <int> q;
        q.push(i);
        vis[i] = true;
        
        while (!q.empty()){
            cnt[i]++;
            int u = q.front();
            q.pop();
            
            have[r[u]] = true;
            for (auto x : pend[r[u]]){
                vis[x] = true;
                q.push(x);
            }
            pend[r[u]].clear();
            
            for (auto [v, c] : adj[u]){
                if (vis[v]) continue;
                if (have[c]){
                    vis[v] = true;
                    q.push(v);
                } else {
                    pend[c].push_back(v);
                }
            }
        }
        
        mn = min(mn, cnt[i]);
    }
    
    vector <int> ans;
    for (int i = 0; i < n; i++){
        if (mn == cnt[i]) ans.push_back(i);
    }
    
    return ans;
}

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