Submission #1231455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231455		SamAnd	Keys (IOI21_keys)	C++20	67 / 100	3101 ms	171080 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 300005;

int n;
vector<pair<int, int> > g[N];

int maxu[N];
bool c[N];
bool cc[N];
vector<int> v[N];
vector<vector<int> > vvv;
int stup(int x, const vector<int>& r)
{
    int ans = 0;
    queue<int> q;
    q.push(x);
    queue<int> qq;
    vector<int> vv;
    int s = x;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        if (c[x])
            continue;
        ++ans;
        vv.push_back(x);
        qq.push(x);
        qq.push(r[x]);
        c[x] = true;
        cc[r[x]] = true;
        maxu[s] = max(maxu[s], maxu[x]);
        if (maxu[s] > s)
        {
            ans = N;
            break;
        }
        while (!v[r[x]].empty())
        {
            q.push(v[r[x]].back());
            v[r[x]].pop_back();
        }
        for (int i = 0; i < sz(g[x]); ++i)
        {
            int h = g[x][i].fi;
            if (cc[g[x][i].se])
                q.push(h);
            else
            {
                qq.push(g[x][i].se);
                v[g[x][i].se].push_back(h);
            }
        }
    }
    while (!qq.empty())
    {
        int x = qq.front();
        qq.pop();
        c[x] = false;
        cc[x] = false;
        v[x].clear();
    }
    vvv.push_back(vv);
    return ans;
}

std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
    n = sz(R);
    int m = sz(U);

	std::vector<int> ans(n, 0);
    for (int i = 0; i < m; ++i)
    {
        int x = U[i];
        int y = V[i];
        if (x == y)
            continue;
        g[x].push_back(m_p(y, C[i]));
        g[y].push_back(m_p(x, C[i]));
    }

    bool ff = false;
    for (int x = 0; x < n; ++x)
    {
        bool f = false;
        for (int i = 0; i < g[x].size(); ++i)
        {
            if (g[x][i].se == R[x])
            {
                f = true;
                break;
            }
        }
        if (!f)
        {
            ff = true;
            break;
        }
    }

    if (ff)
    {
        for (int x = 0; x < n; ++x)
        {
            bool f = false;
            for (int i = 0; i < g[x].size(); ++i)
            {
                if (g[x][i].se == R[x])
                {
                    f = true;
                    break;
                }
            }
            if (!f)
                ans[x] = 1;
        }
        return ans;
    }

    for (int x = 0; x < n; ++x)
    {
        maxu[x] = x;
        c[x] = false;
    }

    vector<int> s;
    for (int x = 0; x < n; ++x)
    {
        s.push_back(stup(x, R));
    }

    int minu = s[0];
    for (int x = 0; x < n; ++x)
        minu = min(minu, s[x]);

    for (int x = 0; x < n; ++x)
    {
        if (s[x] == minu)
        {
            for (int j = 0; j < sz(vvv[x]); ++j)
                ans[vvv[x][j]] = 1;
        }
    }

    return ans;
}

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