Submission #816973

#	Time	Username	Problem	Language	Result	Execution time	Memory
816973		vjudge1	Keys (IOI21_keys)	C++17	9 / 100	100 ms	19944 KiB

keys

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, i, j, sbt = 5, mc = 0, mr = 0, mi;
vector<vector<pair<int, int> > > w;
vector<int> s;
vector<bool> vi, ky;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    n = r.size();
    m = u.size();
    w.resize(n);
    s.resize(n);
    vi.resize(n);
    ky.resize(n);
    mi = n;
    for (i = 0; i < m; i++)
    {
        w[u[i]].push_back({v[i], c[i]});
        w[v[i]].push_back({u[i], c[i]});
        mc = max(mc, c[i]);
    }
    for (i = 0; i < n; i++)
        mr = max(mr, r[i]);
    if (mc <= 29 && mr <= 29)
        sbt = 4;
    if (n <= 2000 && m <= 2000)
        sbt = 3;
    if (n <= 200 && m <= 200)
        sbt = 2;
    if (sbt == 2)
    {
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
                vi[j] = ky[j] = false;
            vi[i] = ky[r[i]] = true;
            queue<int> q;
            q.push(i);
            s[i] = 0;
            while (!q.empty())
            {
                int t = q.front();
                q.pop();
                s[i]++;
                for (auto k : w[t])
                {
                    if (!vi[k.first] && ky[k.second])
                    {
                        q.push(k.first);
                        vi[k.first] = ky[r[k.first]] = true;
                    }
                }
            }
            mi = min(mi, s[i]);
        }
        for (i = 0; i < n; i++)
        {
            if (s[i] == mi)
                s[i] = 1;
            else
                s[i] = 0;
        }
    }
    return s;
}

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