Submission #447191

#	Time	Username	Problem	Language	Result	Execution time	Memory
447191		blue	Keys (IOI21_keys)	C++17	0 / 100	34 ms	60184 KiB

keys

#include "keys.h"
#include <vector>
#include <iostream>
#include <set>
#include <queue>
using namespace std;

const int maxN = 300'000;
const int INF = 1e9;

int N;
int M;







struct edge //store in multiset
{
    int v;
    int c;
};

bool operator < (edge A, edge B)
{
    return A.c < B.c;
}

set<int> good_edge[maxN]; //not label
multiset<edge> bad_edge[maxN]; //not label
set<int> keys[maxN];



vector<int> scc_list[maxN];
vector<int> scc_label(maxN);

void scc_join(int u, int v) //list, label, keys, good edge, bad edge
{
    u = scc_label[u];
    v = scc_label[v];

    if(scc_list[u].size() < scc_list[v].size())
        swap(u, v);


    for(int x: scc_list[v])
    {
        scc_list[u].push_back(x);
        scc_label[x] = u;
    }

    for(int k: keys[v])
    {
        multiset<edge>::iterator it = bad_edge[u].find(edge{-1, k});
        if(it == bad_edge[u].end()) break;

        good_edge[u].insert(it->v);
        bad_edge[u].erase(it);

        keys[u].insert(k);
    }

    for(int g: good_edge[v])
    {
        good_edge[u].insert(g);
    }

    for(edge b: bad_edge[v])
    {
        if(keys[u].find(b.c) == keys[u].end())
        {
            bad_edge[u].insert(b);
        }
        else
        {
            good_edge[u].insert(b.v);
        }
    }

    scc_list[v].clear();
    keys[v].clear();
    bad_edge[v].clear();
    good_edge[v].clear();
}






vector<int> f_parent(maxN);
vector<int> f_label(maxN);
vector<int> descendant_list[maxN];

void merge_lists(int u, int v)
{
    u = scc_label[u];
    v = scc_label[v];

    u = f_label[u];
    v = f_label[v];

    if(descendant_list[u].size() < descendant_list[v].size())
        swap(u, v);

    for(int x: descendant_list[v])
    {
        f_label[x] = u;
        descendant_list[u].push_back(x);
    }
    descendant_list[v].clear();
}

bool isRoot(int u, int v) //return whether u is the root of v.
{
    u = scc_label[u];
    v = scc_label[v];

    return (scc_label[f_parent[u]] == u) && (f_label[u] == f_label[v]);
}





vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    N = r.size();
    M = u.size();


    for(int i = 0; i < N; i++)
    {
        scc_list[i].push_back(i);
        scc_label[i] = i;

        f_parent[i] = i;
        f_label[i] = i;
        descendant_list[i].push_back(i);

        keys[i].insert( r[i] );
    }


    for(int j = 0; j < M; j++)
    {
        if(keys[ u[j] ].find( c[j] ) == keys[ u[j] ].end())
            bad_edge[ u[j] ].insert(edge{v[j], c[j]});
        else
            good_edge[ u[j] ].insert( v[j] );

        if(keys[ v[j] ].find( c[j] ) == keys[ v[j] ].end())
            bad_edge[ v[j] ].insert(edge{u[j], c[j]});
        else
            good_edge[ v[j] ].insert( u[j] );
    }





    for(int i = 0; i < N; i++)
    {
        int I = scc_label[i];

        if(scc_label[f_parent[I]] != I) continue;

        // cerr << '\n';
        // cerr << "I = " << I << '\n';
        //
        // cerr << "good edge = ";
        // for(int G: good_edge[I]) cerr << G << ' ';
        // cerr << '\n';

        set<int> new_good_edge = good_edge[I];

        for(int G: new_good_edge)
        {
            // cerr << "G = " << G << '\n';
            if(isRoot(I, G))
            {
                while(scc_label[G] != scc_label[I])
                {
                    scc_join(G, f_parent[G]);
                    G = f_parent[G];
                }
            }
            else
            {
                f_parent[I] = scc_label[G];
                good_edge[I].erase(G);

                merge_lists(I, G);

                break;
            }
        }
    }

    // for(int i = 0; i < N; i++) cerr << i << ' ' << scc_label[i] << ' ' << scc_label[f_parent[scc_label[i]]] << '\n';

    int min_reach = INF;
    vector<int> res_list;
    for(int i = 0; i < N; i++)
    {
        int I = scc_label[i];
        if(scc_label[f_parent[I]] != I) continue;

        if(scc_list[I].size() > min_reach) continue;
        else if(scc_list[I].size() == min_reach)
        {
            res_list.push_back(i);
        }
        else
        {
            res_list.clear();
            res_list.push_back(i);
            min_reach = scc_list[I].size();
        }
    }

    vector<int> res(N, 0);
    for(int R: res_list) res[R] = 1;

    return res;
}

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:212:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  212 |         if(scc_list[I].size() > min_reach) continue;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
keys.cpp:213:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  213 |         else if(scc_list[I].size() == min_reach)
      |                 ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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