Submission #1024552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024552		12345678	Keys (IOI21_keys)	C++17	37 / 100	3051 ms	32992 KiB

keys

#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5;

int n, m, mn=INT_MAX, p[nx];
vector<pair<int, int>> d[nx];

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n=r.size(), m=u.size();
	for (int i=0; i<m; i++) d[u[i]].push_back({v[i], c[i]}), d[v[i]].push_back({u[i], c[i]});
	for (int i=0; i<n; i++)
    {
        vector<int> k(n), w[n], vs(n);
        queue<int> q;
        int cnt=0;
        vs[i]=1;
        q.push(i);
        while (!q.empty())
        {
            auto u=q.front();
            cnt++;
            q.pop();
            if (!k[r[u]])
            {
                k[r[u]]=1;
                for (auto x:w[r[u]]) if (!vs[x]) vs[x]=1, q.push(x);
            }
            for (auto [v, t]:d[u]) 
            {
                if (!vs[v])
                {
                    if (k[t]) vs[v]=1, q.push(v);
                    else w[t].push_back(v);
                }
            }
        }
        p[i]=cnt;
        //cout<<"debug "<<i<<' '<<cnt<<'\n';
        mn=min(mn, p[i]);
    }
    vector<int> ans;
    for (int i=0; i<n; i++) ans.push_back(mn==p[i]); 
	return ans;
}

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