Submission #1120991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120991		jerzyk	Keys (IOI21_keys)	C++17	9 / 100	588 ms	240304 KiB

keys

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1000'007;
int tab[N], vis[N];
bool czy[N];
int fau[N], siz[N];
set<pair<int, int>> imp[N];
set<int> pos[N], key[N];
vector<pair<int, int>> ed[N]; 
stack<int> sta;

int Find(int v)
{
    if(fau[v] == v) return v;
    return (fau[v] = Find(fau[v]));
}

void Union(int a, int b)
{
    a = Find(a); b = Find(b);
    if(a == b) return;
    if((int)(pos[a].size() + imp[a].size() + key[a].size()) < (int)(pos[b].size() + imp[b].size() + key[b].size()))
        swap(a, b);

    fau[b] = a;
    for(set<int>::iterator it = key[b].begin(); it != key[b].end(); ++it)
    {
        int x = *it;
        set<pair<int, int>>::iterator it2 = imp[a].lower_bound(make_pair(x, 0));
        while(it2 != imp[a].end() && (*it2).st == x)
        {
            pos[a].insert((*it2).st);
            imp[a].erase(it2);
            it2 = imp[a].lower_bound(make_pair(x, 0));
        }
        key[a].insert(x);
    }
    key[b].clear();
    for(set<int>::iterator it = pos[b].begin(); it != pos[b].end(); ++it)
        pos[a].insert(*it);
    pos[b].clear();
    for(set<pair<int, int>>::iterator it = imp[b].begin(); it != imp[b].end(); ++it)
    {
        if(key[a].find((*it).st) != key[a].end())
            pos[a].insert((*it).nd);
        else
            imp[a].insert(*it);
    }
    imp[b].clear();
}

void DFS()
{
    while(sta.size() > 0)
    {
        int v = sta.top();
        vis[v] = 1;
        if((int)pos[v].size() == 0)
        {
            vis[v] = 2;
            sta.pop();
            continue;
        }
        int ne = *(pos[v].begin()); pos[v].erase(pos[v].begin());
        //cerr << "DFS " << v << " " << ne << " vis: " << vis[ne] << "\n";
        ne = Find(ne);
        if(vis[ne] == 2 || ne == v) continue;
        if(vis[ne] == 0)
        {
            sta.push(ne);
            continue;
        }
        sta.pop();
        while(sta.top() != ne)
        {
            Union(v, sta.top());
            sta.pop();
        }
        Union(v, ne);
        sta.pop();
        sta.push(Find(v));
    }
}

vector<int> find_reachable(vector<int> _r, vector<int> _u, vector<int> _v, vector<int> _c)
{
    int n = _r.size(), m = _u.size();
    for(int i = 0; i < m; ++i)
    {
        ed[_u[i] + 1].pb(make_pair(_v[i] + 1, _c[i]));
        ed[_v[i] + 1].pb(make_pair(_u[i] + 1, _c[i]));
    }
    for(int i = 1; i <= n; ++i)
    {
        fau[i] = i; czy[i] = true;
        tab[i] = _r[i - 1];
        key[i].insert(tab[i]);
        for(int j = 0; j < (int)ed[i].size(); ++j)
            if(ed[i][j].nd == tab[i])
                pos[i].insert(ed[i][j].st);
            else
                imp[i].insert(make_pair(ed[i][j].nd, ed[i][j].st));
    }
    for(int i = 1; i <= n; ++i)
    {
        if(vis[i] == 0)
        {
            sta.push(i);
            DFS();
        }
    }
    int mi = n * 10;
    for(int i = 1; i <= n; ++i)
    {
        int v = Find(i);
        if(czy[v] == false) continue;
        ++siz[v];
        for(int j = 0; j < (int)ed[i].size(); ++j)
        {
            int ne = Find(ed[i][j].st);
            if(ne != v && key[v].find(ed[i][j].nd) != key[v].end())
                czy[v] = false;
        }
    }
    for(int i = 1; i <= n; ++i)
        if(Find(i) == i && czy[i])
            mi = min(mi, siz[i]);
    vector<int> answer;
    for(int i = 1; i <= n; ++i)
        if(czy[Find(i)] && siz[Find(i)] == mi)
            answer.pb(1);
        else
            answer.pb(0);
    return answer;
}

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