Submission #502256

#	Time	Username	Problem	Language	Result	Execution time	Memory
502256		PiejanVDC	Keys (IOI21_keys)	C++17	0 / 100	1 ms	204 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;

vector<int> find_reachable(vector<int>r, vector<int>u, vector<int>v, vector<int>c) {
    const int n = (int)r.size();
    int ans[n];
    memset(ans,0,sizeof(ans));
    int mn = INT_MAX;
    vector<pair<int,int>>adj[n];
    for(int i = 0 ; i < n ; i++) {
        adj[u[i]].push_back({v[i],c[i]});
        adj[v[i]].push_back({u[i],c[i]});
    }
    for(int s = 0 ; s < n ; s++) {
        map<int,vector<int>>mp;
        map<int,bool>got;
        queue<int>q;
        bool vis[n];
        int sz = 0;
        memset(vis,0,sizeof(vis));
        while(!q.empty()) {
            int room = q.front();
            q.pop();
            got[r[room]] = 1;
            sz++;
            for(auto nxt : adj[room]) {
                if(vis[nxt.first]) continue;
                if(got[nxt.second]) {
                    vis[nxt.first] = 1;
                    q.push(nxt.first);
                } else mp[nxt.second].push_back(nxt.first);
            }
            vector<int>res = mp[r[room]];
            mp[r[room]].clear();
            for(auto z : res)
                q.push(z);
        }
        if(sz < mn) {
            memset(ans,0,sizeof(ans));
            ans[s] = 1;
            mn = sz;
        } else if(sz == mn) ans[s] = 1;
    }
    vector<int>ret(n);
    for(int i = 0 ; i < n ; i++) ret[i] = ans[i];
    return ret;
}

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