Submission #1037000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037000		aaaaaarroz	Keys (IOI21_keys)	C++17	37 / 100	3022 ms	32812 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