Submission #481466

#	Time	Username	Problem	Language	Result	Execution time	Memory
481466		yungyao	Keys (IOI21_keys)	C++17	37 / 100	3069 ms	27852 KiB

keys

using namespace std;
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>

typedef long long LL;
typedef pair<int,int> pii;
#define pb push_back
#define mkp make_pair
#define F first
#define S second
#define REP(n) for (int __=n;__--;)
#define REP1(i,n) for (int i=1;i<=n;++i)
#define REP0(i,n) for (int i=0;i<n;++i)
typedef vector <int> vi;

#include "keys.h"

vi find_reachable(vi r,vi u,vi v,vi c){
    int n = r.size(),m = c.size();

    vector <vector <pii>> adj(n);
    vector <int> p(n);
    REP0(i,m){
        adj[u[i]].pb(mkp(v[i],c[i]));
        adj[v[i]].pb(mkp(u[i],c[i]));
    }

    int mn = n;
    REP0(i,n){
        vector <bool> unlocked(n,false),vis(n,false);
        vector <vector <int> > que(n);

        queue <int> bfs;
        bfs.push(i);
        vis[i] = true;

        while (!bfs.empty()){
            int x = bfs.front(); bfs.pop();

            if (!unlocked[r[x]]){
                unlocked[r[x]] = true;
                for (auto i:que[r[x]]) if (!vis[i]){
                    vis[i] = true;
                    bfs.push(i);
                }
            }

            for (auto [i,rq]:adj[x]) if (!vis[i]){
                if (unlocked[rq]){
                    vis[i] = true;
                    bfs.push(i);
                }
                else{
                    que[rq].pb(i);
                }
            }
        }

        REP0(j,n) if (vis[j]) ++p[i];
        mn = min(mn,p[i]);
    }

    vector <int> ret(n);
    REP0(i,n) ret[i] = (mn == p[i]);
    return ret;
}

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