Submission #1217679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217679		guagua0407	Keys (IOI21_keys)	C++20	37 / 100	3095 ms	23412 KiB

keys

#include "keys.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    int n=(int)r.size();
    int m=(int)u.size();
    vector<vector<pair<int,int>>> adj(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]});
    }
    vector<int> cnt(n);
    auto go=[&](int st){
        vector<vector<int>> e(n);
        vector<bool> vis(n);
        vector<bool> ok(n);
        queue<int> q;
        vis[st]=true;
        q.push(st);
        while(!q.empty()){
            int v=q.front();
            q.pop();
            cnt[st]++;
            for(auto u:adj[v]){
                if(vis[u.f]) continue;
                if(ok[u.s]){
                    vis[u.f]=true;
                    q.push(u.f);
                }
                else{
                    e[u.s].push_back(u.f);
                }
            }
            if(!ok[r[v]]){
                ok[r[v]]=true;
                for(auto u:e[r[v]]){
                    if(vis[u]) continue;
                    vis[u]=true;
                    q.push(u);
                }
            }
        }
    };
    for(int i=0;i<n;i++){
        go(i);
    }
    int mn=*min_element(all(cnt));
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        if(cnt[i]==mn) ans[i]=1;
    }
	return ans;
}

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