Submission #1011951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011951		boris_mihov	Keys (IOI21_keys)	C++17	37 / 100	3039 ms	39272 KiB

keys

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>

typedef long long llong;
const int MAXN = 300000 + 10;
const int INF  = 1e9;

int n, m;
int p[MAXN];
int c[MAXN];
bool pushed[MAXN];
bool unlocked[MAXN];
std::queue <int> toUnlock;
std::vector <std::pair <int,int>> g[MAXN];
std::vector <std::pair <int,int>> byColor[MAXN];
std::vector <int> find_reachable(std::vector <int> r, std::vector <int> u, std::vector <int> v, std::vector <int> _col)
{
	n = r.size();
    m = u.size();
    for (int i = 0 ; i < n ; ++i)
    {
        c[i + 1] = r[i] + 1;
    }

    for (int i = 0 ; i < m ; ++i)
    {
        byColor[_col[i] + 1].push_back({u[i] + 1, v[i] + 1});
        g[u[i] + 1].push_back({v[i] + 1, _col[i] + 1});
        g[v[i] + 1].push_back({u[i] + 1, _col[i] + 1});
    }

    int min = n;
    std::vector <int> sol;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::fill(pushed + 1, pushed + 1 + n, false);
        std::fill(unlocked + 1, unlocked + 1 + n, false);
        toUnlock.push(i);
        pushed[i] = true;

        while (toUnlock.size())
        {
            p[i]++;
            int node = toUnlock.front();
            toUnlock.pop();
    
            if (!unlocked[c[node]])
            {
                for (const auto &[from, to] : byColor[c[node]])
                {
                    if (pushed[from] ^ pushed[to])
                    {
                        if (pushed[from]) 
                        {
                            toUnlock.push(to);
                            pushed[to] = true;
                        } else 
                        {
                            toUnlock.push(from);
                            pushed[from] = true;
                        }
                    }
                }

                unlocked[c[node]] = true;
            }

            for (const auto &[u, col] : g[node])
            {
                if (!pushed[u] && unlocked[col])
                {
                    pushed[u] = true;
                    toUnlock.push(u);
                }
            }
        }

        min = std::min(min, p[i]);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (p[i] == min)
        {
            sol.push_back(1);
        } else
        {
            sol.push_back(0);
        }
    }

	return sol;
}

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