제출 #795620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795620		caganyanmaz	열쇠 (IOI21_keys)	C++17	37 / 100	3057 ms	37108 KiB

keys

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


constexpr static int SIZE = 300000;
vector<array<int, 2>> g[SIZE];
set<array<int, 2>> pending_edges;
int visited[SIZE];
int keys[SIZE];
int counts[SIZE];
vector<int> r;

int min_count = INT_MAX;
int current_node;

bool dfs(int node)
{
        counts[current_node]++;
        visited[node] = current_node;
        if (counts[node] > min_count)
                counts[current_node] = INT_MAX;
        if (counts[current_node] > min_count)
                return false;
        int key = r[node];
        if (keys[key] != current_node)
        {
                keys[key] = current_node;
                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]] != current_node && !dfs((*it)[1]))
                                return false;
        }

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

vector<int> find_reachable(vector<int> rr, vector<int> u, vector<int> v, vector<int> c)
{
        r = rr;
        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 = n;
        for (int i = 0; i < n; i++)
        {
                visited[i] = -1;
                keys[i] = -1;
        }
        for (int i = 0; i < n; i++)
        {
                current_node = i;
                pending_edges.clear();
                dfs(i);
                min_count = min(min_count, counts[i]);
        }
        vector<int> res(n, 0);

        for (int i = 0; i < n; i++)
                if (counts[i] == min_count)
                        res[i] = 1;
        return res;
}

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