Submission #1075963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075963		jer033	Keys (IOI21_keys)	C++17	37 / 100	3095 ms	25344 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 999'999;

int traverse(int start, vector<int> (&r), vector<vector<pii>> (&edges))
{
    map<int, bool> has_access;
    map<int, vector<int>> will_have_access;
    int n = edges.size();
    vector<bool> rooms_reached(n, 0);
    queue<int> rooms_processed;
    int ans = 1;
    rooms_reached[start] = 1;
    rooms_processed.push(start);
    while (!rooms_processed.empty())
    {
        int room = rooms_processed.front();
        rooms_processed.pop();

        int new_key = r[room];
        has_access[new_key] = 1;
        for (int neigh: will_have_access[new_key])
        {
            if (rooms_reached[neigh] == 0)
            {
                rooms_reached[neigh] = 1;
                rooms_processed.push(neigh);
                ans++;
            }
        }
        will_have_access[new_key] = {};
        
        for (pii x: edges[room])
        {
            int neigh = x.first;
            int required = x.second;
            if (rooms_reached[neigh] == 0)
            {
                if (has_access[required])
                {
                    rooms_reached[neigh] = 1;
                    rooms_processed.push(neigh);
                    ans++;
                }
                else
                    will_have_access[required].push_back(neigh);
            }
        } 
    }
    return ans;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    int n = r.size();
    vector<vector<pii>> edges(n);
    int m = u.size();
    for (int i=0; i<m; i++)
    {
        int uu = u[i];
        int vv = v[i];
        int corridor = c[i];
        edges[uu].push_back({vv, corridor});
        edges[vv].push_back({uu, corridor});
    }
    vector<int> count_of_rooms_reached(n);
    for (int i=0; i<n; i++)
        count_of_rooms_reached[i] = traverse(i, r, edges);
    
    int mini = INF;
    for (int i=0; i<n; i++)
        mini = min(mini, count_of_rooms_reached[i]);
    
    vector<int> ans(n, 0);
    for (int i=0; i<n; i++)
        if (count_of_rooms_reached[i]==mini)
            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