Submission #712397

#	Time	Username	Problem	Language	Result	Execution time	Memory
712397		danikoynov	Keys (IOI21_keys)	C++17	0 / 100	30 ms	47264 KiB

keys

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

using namespace std;


const int maxn = 3e5 + 10;

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

    int cnt_edges_v = 0, cnt_edges_u = 0;
    for (int key : cp[v].keys)
        cnt_edges_v += cp[v].edges[key].size();
    for (int key : cp[u].keys)
        cnt_edges_u += cp[u].edges[key].size();

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

    if (cnt_edges_v > cnt_edges_u)
        swap(cp[v].edges, cp[u].edges);

    for (int key : cp[u].keys)
        for (int v : cp[v].edges[key])
            cp[u].edges[key].push_back(v);

    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)
        {
            if (cp[cur].edges[key].empty())
                continue;
            int to = find_leader(cp[cur].edges[key].back());
            cp[cur].edges[key].pop_back();
            if (to == cur)
                continue;
            int up = to;
            while(cp[up].parent != -1)
                up = cp[up].parent;
            if (up != cur)
            {
                cp[cur].parent = to;
                break;
            }

            while(to != cur)
            {
                int to_go = cp[to].parent;
                merge_components(to, to_go);
                to = to_go;
            }
            q.push(cur);
            break;
        }
    }

    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;

        for (int vertex : cp[v].vertices)
            ans[vertex] = 1;
    }

    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:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < u.size(); i ++)
      |                     ~~^~~~~~~~~~
keys.cpp:135:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |         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