Submission #805635

#	Time	Username	Problem	Language	Result	Execution time	Memory
805635		raysh07	Keys (IOI21_keys)	C++17	37 / 100	3068 ms	36864 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;
            vis[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]]){
                if (vis[x]) continue;
                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(1);
        else ans.push_back(0);
    }
    
    return ans;
}

// int main(){
//     int n, m; cin >> n >> m;
    
//     vector <int> r(n), u(m), v(m), c(m);
//     for (auto &x : r) cin >> x;
    
//     for (int i = 0; i < m; i++){
//         cin >> u[i] >> v[i] >> c[i];
//     }
    
//     vector <int> ans = find_reachable(r, u, v, c);
//     for (auto x : ans) cout << x << " ";
//     cout << "\n";
//     return 0;
// }

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