Submission #817075

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

keys

#include <iostream>
#include <vector>
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 (sbt == 3)
    {
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
                vi[j] = ky[j] = false;
            vi[i] = ky[r[i]] = true;
            vector<int> q, nq;
            q.push_back(i);
            while (true)
            {
                nq = {};
                int te = q.size();
                for (auto t : q)
                {
                    for (auto k : w[t])
                    {
                        if (!vi[k.first] && ky[k.second])
                        {
                            nq.push_back(k.first);
                            vi[k.first] = ky[r[k.first]] = true;
                        }
                    }
                }
                if (nq.size() == 0)
                    break;
                for (auto t : nq)
                    q.push_back(t);
            }
            s[i] = q.size();
            mi = min(mi, s[i]);
        }
        for (i = 0; i < n; i++)
        {
            if (s[i] == mi)
                s[i] = 1;
            else
                s[i] = 0;
        }
    }
    return s;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:41:21: warning: unused variable 'te' [-Wunused-variable]
   41 |                 int te = q.size();
      |                     ^~

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