Submission #712415

#	Time	Username	Problem	Language	Result	Execution time	Memory
712415		danikoynov	Keys (IOI21_keys)	C++17	0 / 100	1696 ms	468836 KiB

keys

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

using namespace std;


const int maxn = 3e5 + 10;

struct component
{
    map < int, vector < int > > edges, stored;
    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];

void merge_components(int v, int u)
{
    ///cout << "merge " << v << " " << u << endl;


    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);




    for (int key = 0; key < n; key ++)
        for (int ver : cp[v].edges[key])
        {
            ///cout << "from " << v << " to " << u << " " << ver << endl;
            cp[u].edges[key].push_back(ver);
        }
    for (int key = 0; key < n; key ++)
        for (int ver : cp[v].stored[key])
        {
            ///cout << "from " << v << " to " << u << " " << ver << endl;
            cp[u].edges[key].push_back(ver);
        }
    for (int key = 0; key < n; key ++)
    {
        cp[u].stored[key].clear();
        for (int ver : cp[u].stored[key])
        {
            ///cout << "from " << v << " to " << u << " " << ver << endl;
            cp[u].edges[key].push_back(ver);
        }
    }


    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);

    lead[v] = u;
}


int find_leader(int v)
{
    if (v == lead[v])
        return v;
    return (lead[v] = find_leader(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 < 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[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);
    }

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        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].stored[key].push_back(cp[cur].edges[key].back());
                ///cout << "store " << cur << " " << key << " " << cp[cur].edges[key].back() << endl;
                cp[cur].edges[key].pop_back();

                if (to == cur)
                    continue;
                ///cout << cur << " :: " << to << endl;
                int up = to;
                while(cp[up].parent != -1)
                {
                    up = cp[up].parent;
                    ///cout << up << endl;
                }
                if (up != cur)
                {
                    cp[cur].parent = to;
                    //cout << cur << " --- " << up << endl;
                    done = true;
                    break;
                }

                while(to != cur)
                {
                    int to_go = cp[to].parent;
                    merge_components(to, to_go);
                    to = to_go;
                }
                q.push(cur);
                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 v = find_leader(i);
        if (cp[v].parent != -1)
            continue;
        least = min(least, (int)cp[v].vertices.size());
    }

    for (int i = 0; i < n; i ++)
    {
        int v = find_leader(i);
        if (cp[v].parent != -1)
            continue;
        if (cp[v].vertices.size() != least)
            continue;
        ///cout << v << " " << cp[v].vertices.size() << endl;
        for (int vertex : cp[v].vertices)
            ans[vertex] = 1;
        cp[v].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:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < u.size(); i ++)
      |                     ~~^~~~~~~~~~
keys.cpp:171:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  171 |         if (cp[v].vertices.size() != least)
      |             ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

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