Submission #447218

#	Time	Username	Problem	Language	Result	Execution time	Memory
447218		blue	Keys (IOI21_keys)	C++17	0 / 100	7 ms	10956 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);


set<int> curr_visited;
set<int> curr_inserted;





vector<int> new_good_edge;



vector<int> f_parent(maxN);

void scc_join(int u, int v) //list, label, *keys, good edge, bad edge
{
    int new_f_parent;

    u = scc_label[u];
    v = scc_label[v];

    if(f_parent[u] == v)
        new_f_parent = f_parent[v];
    else
        new_f_parent = f_parent[u];


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

    // cerr << "while joining, small = " << v << ", large = " << u << '\n';

    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;

        if(curr_inserted.find(it->v) == curr_visited.end())
        {
            good_edge[u]->insert(it->v);
            curr_inserted.insert(it->v);
        }
        // new_good_edge.push_back(it->v);

        bad_edge[u]->erase(it);

        keys[u]->insert(k);
    }

    for(int g: *good_edge[v])
    {
        if(curr_inserted.find(u) == curr_visited.end())
        {
            good_edge[u]->insert(u);
            curr_inserted.insert(u);
        }
    }

    for(edge b: *bad_edge[v])
    {
        if(keys[u]->find(b.c) == keys[u]->end())
        {
            bad_edge[u]->insert(b);
        }
        else
        {
            if(curr_inserted.find(b.v) == curr_visited.end())
            {
                good_edge[u]->insert(b.v);
                curr_inserted.insert(b.v);
            }
            // new_good_edge.push_back(b.v);
        }
    }

    scc_list[v]->clear();
    keys[v]->clear();
    bad_edge[v]->clear();
    good_edge[v]->clear();

    for(int x: *scc_list[v])
    {
        scc_list[x] = scc_list[u];
        keys[x] = keys[u];
        bad_edge[v] = bad_edge[u];
        good_edge[v] = good_edge[u];
    }

    f_parent[scc_label[u]] = new_f_parent;
}






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)
{
    // cerr << "A\n";
    N = r.size();
    M = u.size();


    for(int i = 0; i < N; i++)
    {
        good_edge[i] = new set<int>;
        bad_edge[i] = new multiset<edge>;
        keys[i] = new set<int>;
        scc_list[i] = new vector<int>;

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

    // cerr << "B\n";


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

    // cerr << "C\n";





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


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

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

        // new_good_edge.clear();

        curr_visited.clear();
        curr_inserted.clear();
        for(int g: *good_edge[I]) curr_inserted.insert(g);

        while(!good_edge[I]->empty())
        {
            // cerr << "new good edge: (before) ";
            // for(int n1: new_good_edge) cerr << n1 << ' ';
            // cerr << '\n';


            I = scc_label[I];

            int G = scc_label[*good_edge[I]->rbegin()];
            good_edge[I]->erase(*good_edge[I]->rbegin());

            // cerr << "entering " << I << ' ' << G << '\n';

            if(curr_visited.find(G) != curr_visited.end())
            {
                good_edge[I]->erase(G);
                continue;
            }
            else
            {
                curr_visited.insert(G);
            }

            if(scc_label[I] == scc_label[G]) continue;
            // cerr << "Good edge back = " << G << '\n';


            // cerr << "g = " << G << '\n';

            if(isRoot(I, G))
            {
                // cerr << "case 1\n";
                // cerr << "good edge G\n";
                // for(int g1: *good_edge[G]) cerr << g1 << ' ';
                // cerr << '\n';

                // cerr << "compressing " << G << "\n";
                while(scc_label[G] != scc_label[I])
                {
                    // cerr << "merging SCCs " << scc_label[G] << ' ' << scc_label[f_parent[G]] << '\n';
                    // cerr << "join " << G << ' ' << f_parent[G] << '\n';
                    scc_join(G, f_parent[G]);
                    // cerr << "hello?\n";
                    G = scc_label[G];
                    I = scc_label[I];
                }

                // cerr << "gx = ";
                // for(int gx: new_good_edge) cerr << gx << ' ';
                // cerr << '\n';

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

                good_edge[I]->erase(G);

                // cerr << "end of case 1\n";
            }
            else
            {
                // cerr << "case 2\n";
                // cerr << "making " << scc_label[G] << " the parent of " << I << '\n';

                I = scc_label[I];

                f_parent[I] = scc_label[G];
                good_edge[I]->erase(G);

                G = scc_label[G];

                merge_lists(I, G);
                I = scc_label[I];
                G = scc_label[G];

                // cerr << "breaking at G = " << G << '\n';
                //
                //
                //
                //
                // cerr << "\n ! \n !\n";
                // for(int j = 0; j < N; j++) cerr << j << ' ' << scc_label[j] << ' ' << scc_label[f_parent[scc_label[j]]] << '\n';
                // cerr << "\n ! \n !";

                break;
            }

            // cerr << "new good edge: (after) ";
            // for(int n1: new_good_edge) cerr << n1 << ' ';
            // cerr << '\n';

            // cerr << "end of loop\n";
        }
        // cerr << "end of other loop\n";
    }

    // cerr << "D\n";

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

    // cerr << "E\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();
        }
    }

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

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

    // cerr << "F\n";

    return res;
}

Compilation message (stderr)

keys.cpp: In function 'void scc_join(int, int)':
keys.cpp:95:13: warning: unused variable 'g' [-Wunused-variable]
   95 |     for(int g: *good_edge[v])
      |             ^
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:363:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  363 |         if(scc_list[I]->size() > min_reach) continue;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
keys.cpp:364:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  364 |         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