Submission #1048139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048139		sonamoo	Keys (IOI21_keys)	C++17	9 / 100	48 ms	17236 KiB

keys

#include <bits/stdc++.h>
#define SIZE 2005

using namespace std;

int n , m;
int ret[SIZE] , vis[SIZE] , res;
vector<pair<int,int> > graph[SIZE];
vector<int> wait[SIZE];
int key[SIZE] , chk[SIZE];
queue<int> q;

vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	vector<int> ans(r.size(), 1);
    n = r.size() , m = u.size();
    for (int i = 0; i < m; i++) {
        int a = u[i] , b = v[i];
        graph[a].push_back({b,c[i]}); graph[b].push_back({a,c[i]});
    }

    int mi = 1e9;
    for (int S = 0; S < n; S++) {
        memset(vis , 0 , sizeof(vis));
        memset(key , 0 , sizeof(key));
        memset(chk , 0 , sizeof(chk));
        for (int i = 0; i < n; i++) wait[i].clear();

        q.push(S), key[r[S]]=1, vis[S]=1, res=0;
        while(!q.empty()) {
            int here = q.front(); q.pop();
            res++;
            if (key[r[here]]==0) {
                key[r[here]]=1;
                for (auto t : wait[r[here]]) {
                    q.push(t);
                    vis[t]=1;
                }
            }
            for (auto t : graph[here]) {
                int there = t.first , isp = t.second;
                if (key[isp]==1 && vis[there]==0) {
                    vis[there]=1;
                    q.push(there);
                }
                else {
                    if (chk[there] == 0) {
                        chk[there]=1;
                        wait[isp].push_back(there);
                    }
                }
            }
        }
        ret[S] = res;
        mi = min(mi , res);
    }

    for (int i = 0; i < n; i++) if (ret[i] != mi) ans[i] = 0;

	return ans;
}

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