Submission #802967

#	Time	Username	Problem	Language	Result	Execution time	Memory
802967		SamAnd	Keys (IOI21_keys)	C++17	37 / 100	92 ms	18448 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 = 2003;

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

bool c[N];
bool cc[N];
vector<int> v[N];
int stup(int x, const vector<int>& r)
{
    int ans = 0;
    queue<int> q;
    q.push(x);
    queue<int> qq;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        if (c[x])
            continue;
        ++ans;
        qq.push(x);
        qq.push(r[x]);
        c[x] = true;
        cc[r[x]] = true;
        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();
    }
    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)
    {
        g[u[i]].push_back(m_p(v[i], c[i]));
        g[v[i]].push_back(m_p(u[i], c[i]));
    }

    vector<int> s;
    for (int i = 0; i < n; ++i)
        s.push_back(stup(i, r));

    int minu = s[0];
    for (int i = 0; i < n; ++i)
    {
        minu = min(minu, s[i]);
    }
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == minu)
            ans[i] = 1;
    }

	return ans;
}

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