Submission #761497

#	Time	Username	Problem	Language	Result	Execution time	Memory
761497		caganyanmaz	Keys (IOI21_keys)	C++17	37 / 100	154 ms	21640 KiB

keys

#include <bits/stdc++.h>
#define pb push_back
using namespace std;


constexpr static int SIZE = 2010;

vector<array<int, 2>> g[SIZE];
set<array<int, 2>> pending_edges;
bitset<SIZE> visited;
vector<int> rr;
bitset<SIZE> keys;
int current_node;

void dfs(int node)
{
        visited[node] = true;
        int key = rr[node];
        if (!keys[key])
        {
                keys[key] = true;
                array<int, 2> sss = {key, 0};
                for (auto it = pending_edges.lower_bound(sss); it != pending_edges.end() && (*it)[0] == key; it++)
                        if (!visited[(*it)[1]])
                                dfs((*it)[1]);
        }

        for (auto [c, k] : g[node])
        {
                if (visited[c])
                        continue;
                if (keys[k])
                        dfs(c);
                else
                        pending_edges.insert({k, c});
        }
}

int find_count(int node)
{
        visited.reset();
        keys.reset();
        pending_edges.clear();
        current_node = node;
        dfs(node);
        return visited.count();
}


vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
        rr = r;
        int n = r.size(), m = u.size();
        for (int i = 0; i < m; i++)
        {
                g[v[i]].pb({u[i], c[i]});
                g[u[i]].pb({v[i], c[i]});
        }
        int min_count = INT_MAX;
        vector<int> counts(n);
        for (int i = 0; i < n; i++)
        {
                counts[i] = find_count(i);
                min_count = min(min_count, counts[i]);
        }
        vector<int> res(n);
        for (int i = 0; i < n; i++)
                if (counts[i] == min_count)
                        res[i] = 1;
        return res;
}


#ifdef __DEBUG__
int main()
{
        int n, m;
        cin >> n >> m;
        vector<int> r(n), u(m), v(m), c(m);
        for (int& i : r) cin >> i;
        for (int i = 0; i < m; i++)
                cin >> u[i] >> v[i] >> c[i];
        vector<int> res = find_reachable(r, u, v, c);
        for (int i : res)
                cout << i << " ";
        cout << "\n";
}
#endif

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