Submission #1270968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270968		nerrrmin	Keys (IOI21_keys)	C++20	37 / 100	3106 ms	302300 KiB

keys

#include <vector>
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, a[maxn];
vector < pair < int, int > > e[maxn];
map < int, int > mp;
vector < int > keys[maxn];
int p[maxn], reachable[maxn], sz[maxn];
int find_leader(int i)
{
    if(p[i] == i)return i;
    return (p[i] = find_leader(p[i]));
}
bool connected(int i, int j)
{
    return (find_leader(i) == find_leader(j));
}
int used[maxn];
deque < int > col;
void connect(int i, int j)
{
    i = find_leader(i);
    j = find_leader(j);
    if(i == j)return;
    if(reachable[j])swap(i, j);
   // cout << " connect " << i << " " << j << endl;
    p[j] = i;
    reachable[i] = max(reachable[i], reachable[j]);
    sz[i] += sz[j];
    for (auto x: keys[j])
    {
        if(used[x])continue;
       // cout << x << endl;
        keys[i].pb(x);
        if(reachable[i])col.pb(x);
    }
    //cout << " and end? " << endl;
}
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 < n; ++ i)
        a[i] = r[i];
    for (int i = 0; i < m; ++ i)
    {
        e[c[i]].pb(make_pair(u[i], v[i]));
    }
    vector < pair < int, int > > ans;
    int worst = 1e9;
    for (int s = 0; s < n; ++ s)
    {
        //cout << "!!!! " << s << endl;
        col.clear();
        for (int i = 0; i < n; ++ i)
        {
            used[i] = 0;
            p[i] = i;
            sz[i] = 1;
            keys[i].clear();
            if(i == s)
            {
                reachable[i] = 1;
                col.pb(a[i]);
            }
            else reachable[i] = 0;
            keys[i].pb(a[i]);
        }
        while(!col.empty())
        {
            int w = col.front();
            col.pop_front();
          //  cout << "working w colour" <<  w << endl;
            used[w] = 1;
            for (auto &[from, to]: e[w])
            {
               // cout << from << " ,  " << to << endl;
                if(connected(from, to))continue;
              //  cout << from << " " << to << endl;
                connect(from, to);
            }
          //  cout << "lft heree " << endl;
        }
       // cout << " ended fr " << endl;
        int lead = find_leader(s);
        ans.pb({sz[lead], s});
        worst = min(worst, sz[lead]);
       // cout << "ANSWER " << s << " IS " << sz[lead] << endl;
    }
   vector < int > res(n, 0);
    for (auto &[score, i]: ans)
        if(score == worst)res[i] = 1;
	return res;
}

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