Submission #712435

#	Time	Username	Problem	Language	Result	Execution time	Memory
712435		danikoynov	Keys (IOI21_keys)	C++17	37 / 100	3066 ms	98652 KiB

keys

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

using namespace std;


const int maxn = 3e5 + 10;

struct component
{
    vector < pair < int, int > > edges, stored;
    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]));
}
void merge_components(int v, int u)
{

    ///cout << "merge " << v << " " << u << endl;
    ///cout << find_leader(v) << " is " << find_leader(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 (pair < int, int > cur : cp[v].edges)
        cp[u].edges.push_back(cur);
    for (pair < int, int > cur : cp[v].stored)
        cp[u].edges.push_back(cur);
    for (pair < int, int > cur : cp[u].stored)
        cp[u].edges.push_back(cur);

    cp[u].stored.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);

    lead[v] = u;
}



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.push_back(nb);
        }
        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();
        if (cur != find_leader(cur))
            continue;

        while(!cp[cur].edges.empty())
        {
            pair < int, int > cur_edge = cp[cur].edges.back();
            cp[cur].edges.pop_back();
            cp[cur].stored.push_back(cur_edge);
            if (cp[cur].keys.find(cur_edge.second) == cp[cur].keys.end())
            {
                continue;
            }
            int to = cur_edge.first;
            ///cout << "edge " << cur << " " << to << endl;
            to = find_leader(to);

            ///cout << "store " << cur << " " << key << " " << cp[cur].edges[key].back() << endl;

            if (to == cur)
                continue;
            ///cout << cur << " :: " << to << endl;
            int up = to;
            while(cp[up].parent != -1)
            {
                up = cp[up].parent;
                up = find_leader(up);
                ///cout << up << endl;
            }
            if (up != cur)
            {
                cp[cur].parent = to;
                ///to = find_leader(to);
                //cout << cur << " --- " << up << endl;
                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);

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

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