Submission #447072

#	Time	Username	Problem	Language	Result	Execution time	Memory
447072		blue	Keys (IOI21_keys)	C++17	0 / 100	32 ms	47284 KiB

keys

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

struct corridor
{
    int v;
    int c;
};

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

const int maxN = 300'000;
int N;
int M;



struct out_comp
{
    int i; //i = scc root of component
};

bool operator < (out_comp A, out_comp B)
{
    return A.i < B.i;
};

set<int> leaf_components; //FG roots without good edges
set<int> out_components; //FG roots with good edges



vector<int> scc_parent(maxN);
vector<int> scc_size(maxN, 1);

multiset<corridor> bad_corridors[maxN]; //nodes, not labels
set<int> good_corridors[maxN];
set<int> keys[maxN];

int scc_root(int u)
{
    while(scc_parent[u] != u) u = scc_parent[u];
    return u;
}








vector<int> func_parent(maxN); //all are scc roots
vector<int> func_root(maxN);



void add_good_edge(int u, int v)
{
    u = scc_root(u);
    v = scc_root(v);

    if(u == v) return;

    good_corridors[u].insert(v);

    if(leaf_components.find(u) != leaf_components.end())
    {
        leaf_components.erase(u);
        out_components.insert(u);
    }
}




void scc_join(int u, int v)
{
    u = scc_root(u);
    v = scc_root(v);

    if(u == v) return;

    if(scc_size[u] < scc_size[v]) swap(u, v);

    scc_parent[v] = u;
    scc_size[u] += scc_size[v];

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

            add_good_edge(u, it->v);

            bad_corridors[u].erase(it);
        }

        keys[u].insert(k);
    }
    keys[v].clear();


    for(corridor d: bad_corridors[v])
    {
        // if(scc_root(d.v) == scc_root(d.u)) continue;
        if(keys[u].find(d.c) == keys[u].end())
        {
            bad_corridors[u].insert(d);
        }
        else
        {
            add_good_edge(u, d.v);
        }
    }

    for(int h: good_corridors[v])
    {
        good_corridors[u].insert(h);
    }
}

bool scc_same(int u, int v)
{
    return scc_root(u) == scc_root(v);
}





void execute(int x, int y) //add edge x -> y;
{
    x = scc_root(x);
    y = scc_root(y);

    if(func_root[y] != x)
    {
        out_components.erase(x);
        func_parent[x] = y;
        func_root[x] = y;
    }
    else if(func_root[y] == x)
    {
        vector<int> mergers(1, x);
        for(int z = y; z != x; z = func_parent[ scc_root(z) ]) mergers.push_back(z);

        for(int i = 0; i+1 < mergers.size(); i++)
        {
            scc_join(mergers[i], mergers[i+1]);
        }
    }
}



vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    // cerr << "check 1\n";
    N = r.size();
    M = u.size();

    for(int i = 0; i < N; i++)
    {
        scc_parent[i] = i;
        func_parent[i] = i;
        func_root[i] = i;
    }

    // cerr << "check 2\n";



    for(int j = 0; j < M; j++)
    {
        if(r[ u[j] ] == c[j])
            good_corridors[ u[j] ].insert( v[j] );
        else
            bad_corridors[ u[j] ].insert(corridor{v[j], c[j]});

        if(r[ v[j] ] == c[j])
            good_corridors[ v[j] ].insert( u[j] );
        else
            bad_corridors[ v[j] ].insert(corridor{u[j], c[j]});
    }

    // cerr << "check 3\n";

    for(int i = 0; i < N; i++)
    {
        if(good_corridors[i].size() > 0)
            out_components.insert(i);
        else
            leaf_components.insert(i);
    }

    // cerr << "check 4\n";

    while(out_components.size() >= 1)
    {
        int x = *out_components.begin();
        int y = *good_corridors[x].begin();

        out_components.erase(x);
        good_corridors[x].erase(y);

        if(good_corridors[x].size() >= 1) out_components.insert(x);
        else leaf_components.insert(x);

        execute(scc_root(x), scc_root(y)); //add an edge x -> y
    }

    // cerr << "check 5\n";

    vector<int> res_list;

    int min_reach = 1e9;
    for(int i = 0; i < N; i++)
    {
        int I = scc_root(i);

        while(!good_corridors[I].empty())
        {
            int x = *good_corridors[I].begin();
            if(scc_root(x) == I)
            {
                good_corridors[I].erase(x);
                continue;
            }
            break;
        }

        if(!good_corridors[I].empty() || scc_root(func_parent[i]) != scc_root(i) )
        {
            // cerr << "i = " << i << ", this is not a root\n";
            continue;
        }


        if(scc_size[I] > min_reach) continue;
        else if(scc_size[I] == min_reach)
        {
            // cerr << "case Z\n";
            res_list.push_back(i);
            // cerr << "RL = ";
            // for(int r1: res_list) cerr << r1 << ' ';
            // cerr << '\n';
        }
        else
        {
            // cerr << "case Y\n";
            res_list.clear();
            res_list.push_back(i);
            min_reach = scc_size[I];
        }

        // cerr << "i = " << i << ", reachability = " << scc_size[I] << '\n';

    }

    // cerr << "check 6\n";



    // for(int i = 0; i < N; i++) cerr << "root of " << i << " = " << scc_root(i) << '\n';
    // for(int i = 0; i < N; i++) cerr << "FG parent of " << scc_root(i) << " = " << func_parent[i] << '\n';

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

    return res;
}

Compilation message (stderr)

keys.cpp: In function 'void execute(int, int)':
keys.cpp:156:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |         for(int i = 0; i+1 < mergers.size(); i++)
      |                        ~~~~^~~~~~~~~~~~~~~~

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