Submission #436251

#	Time	Username	Problem	Language	Result	Execution time	Memory
436251		CodePlatina	Keys (IOI21_keys)	C++17	37 / 100	2579 ms	30344 KiB

keys

#include <vector>
#include <algorithm>
#include <tuple>
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ff first
#define ss second

using namespace std;

const int INF = (int)1e9 + 7;
vector<pii> gph[303030];

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    int n = r.size();
    int m = u.size();
    for(int i = 0; i < m; ++i)
    {
        gph[u[i]].push_back({v[i], c[i]});
        gph[v[i]].push_back({u[i], c[i]});
    }

    int cnt[n]{};
    int mn = n;
    for(int x = 0; x < n; ++x)
    {
        bool vst[n]{};
        bool col[n]{};
        vector<int> Q;
        vector<int> ls[n];
        Q.push_back(x);
        while(Q.size())
        {
            int i = Q.back(); Q.pop_back();
            if(vst[i]) continue;
            vst[i] = true;
            if(!col[r[i]])
            {
                for(auto j : ls[r[i]]) Q.push_back(j);
                col[r[i]] = true;
            }
            for(auto [j, e] : gph[i])
            {
                if(col[e]) Q.push_back(j);
                else ls[e].push_back(j);
            }
        }
        for(int i = 0; i < n; ++i) if(vst[i]) ++cnt[x];
        mn = min(mn, cnt[x]);
    }

    vector<int> ans(n);
    for(int i = 0; i < n; ++i) if(cnt[i] == mn) ans[i] = 1;
    return ans;
}

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