Submission #712470

#	Time	Username	Problem	Language	Result	Execution time	Memory
712470		danikoynov	Keys (IOI21_keys)	C++17	37 / 100	2598 ms	2097152 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"

using namespace std;


const int maxn = 3e5 + 10;

struct component
{
    unordered_map < int, vector < int > > edges;
    unordered_set < int > keys;
    vector < int > vertices;
    int parent, cnt_ver;
    int index;
};

component cp[maxn];
int n, ver_index[maxn];
vector < pair < int, int > > graph[maxn];
vector < int > ans;

int lead[maxn];

int find_leader(int v)
{
    if (v == lead[v])
        return v;
    return (lead[v] = find_leader(lead[v]));
}
int max_key;
void merge_components(int v, int u)
{
    //cout << "merge " << v << " " << u << endl;
    //cout << find_leader(v) << " is " << find_leader(u) << endl;

    int cnt0 = 0, cnt1 = 0;
    for (int key = 0; key < max_key; key ++)
    {
        cnt0 += cp[v].edges[key].size();
        cnt1 += cp[u].edges[key].size();
    }
    if (cnt0 > cnt1)
    {
        swap(cp[v].edges, cp[u].edges);
    }
    for (int key = 0; key < max_key; key ++)
    {
        for (int ver : cp[v].edges[key])
        {
            ///cout << "from " << v << " to " << u << " " << ver << endl;
            cp[u].edges[key].push_back(ver);
        }
        cp[v].edges[key].clear();
    }


    if (cp[u].keys.size() < cp[v].keys.size())
        swap(cp[u].keys, cp[v].keys);
    for (int key : cp[v].keys)
        cp[u].keys.insert(key);
    cp[v].keys.clear();
    if (cp[v].vertices > cp[u].vertices)
        swap(cp[v].vertices, cp[u].vertices);
    for (int vertex : cp[v].vertices)
        cp[u].vertices.push_back(vertex);
    cp[v].vertices.clear();
    lead[v] = u;
}


int cp_lead[maxn];

int find_cp_leader(int v)
{
    if (v == cp_lead[v])
        return v;
    return (cp_lead[v] = find_cp_leader(cp_lead[v]));
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    n = r.size();
    ans.resize(n);
    for (int i = 0; i < n; i ++)
    {
        max_key = max(max_key, r[i] + 1);
    }
    for (int i = 0; i < u.size(); i ++)
    {
        graph[u[i]].push_back({v[i], c[i]});
        graph[v[i]].push_back({u[i], c[i]});
    }

    queue < int > q;
    for (int i = 0; i < n; i ++)
    {

        lead[i] = i;
        cp_lead[i] = i;
        cp[i].keys.insert(r[i]);
        for (pair < int, int > nb : graph[i])
        {
            cp[i].edges[nb.second].push_back(nb.first);
        }
        cp[i].parent = -1;
        cp[i].cnt_ver = 1;
        cp[i].vertices.push_back(i);
        cp[i].index = i;
        ver_index[i] = i;
        q.push(i);
    }
int op = 0;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        if (cur != find_leader(cur))
            continue;
            ///cout << "cur " << cur << endl;
        op ++;
        if (op > (n + v.size()) * 2)
            exit(0);
        ///cout << cur << " :: " << cp[cur].parent << endl;
        for (int key : cp[cur].keys)
        {
            bool done = false;
            while(!cp[cur].edges[key].empty())
            {

                int to = cp[cur].edges[key].back();
                ///cout << "edge " << cur << " " << to << endl;
                to = find_leader(to);

                cp[cur].edges[key].pop_back();
                ///cout << "store " << cur << " " << key << " " << cp[cur].edges[key].back() << endl;
                if (to == cur)
                    continue;
                ///cout << cur << " :: " << to << endl;
                int up = find_cp_leader(to);

                if (up != cur)
                {
                    cp[cur].parent = to;
                    cp_lead[cur] = to;
                    ///to = find_leader(to);
                    //cout << cur << " --- " << up << endl;
                    done = true;
                    break;
                }

                while(to != cur)
                {
                    int to_go = cp[to].parent;
                    to_go = find_leader(to_go);
                    ///cout << to << " compare " << cur << endl;
                    merge_components(to, to_go);
                    to = to_go;
                }
                q.push(cur);
                done = true;
                break;
            }
            if (done)
                break;
        }
    }

    /**for (int key = 0; key < n; key ++)
        for (int ver : cp[4].edges[key])
            cout << ver << " :: " << endl;*/
    int least = n + 1;
    for (int i = 0; i < n; i ++)
    {
        int ver = find_leader(i);
        if (cp[ver].parent != -1)
            continue;
        least = min(least, (int)cp[ver].vertices.size());
    }

    for (int i = 0; i < n; i ++)
    {
        int ver = find_leader(i);
        if (cp[ver].parent != -1)
            continue;
        if (cp[ver].vertices.size() != least)
            continue;
        ///cout << v << " " << cp[v].vertices.size() << endl;
        for (int vertex : cp[ver].vertices)
            ans[vertex] = 1;
        cp[ver].vertices.clear();
    }

    return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < u.size(); i ++)
      |                     ~~^~~~~~~~~~
keys.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         if (op > (n + v.size()) * 2)
      |             ~~~^~~~~~~~~~~~~~~~~~~~
keys.cpp:185:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  185 |         if (cp[ver].vertices.size() != least)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

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