Submission #1062561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062561		j_vdd16	Keys (IOI21_keys)	C++17	37 / 100	3004 ms	26236 KiB

keys

#include "keys.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

int n, m;
vvii adj;
vi succ;

vi find_reachable(vi r, vi u, vi v, vi c) {
	//std::vector<int> ans(r.size(), 1);

    n = r.size();
    adj = vvii(n);
    succ = vi(n);

    m = u.size();
    loop(i, m) {
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }

    // vi ans;
    // loop(i, n) {
    //     int key = r[i];
    //     int next = -1;
    //     for (auto [room, lock] : adj[i]) {
    //         if (lock == key)
    //             next = room;
    //     }

    //     if (next == -1)
    //         ans.push_back(i);
    //     else
    //         succ[i] = next;
    // }

    // if (ans.size())
    //     return ans;

    int minCount = n;
    vi ans;

    loop(i, n) {
        set<int> keys;

        map<int, vi> todo;
        vb vis(n);
        stack<int> s;
        s.push(i);

        int count = 0;
        while (s.size()) {
            int node = s.top();
            s.pop();

            if (vis[node]) 
                continue;
            
            count++;
            vis[node] = true;

            int key = r[node];
            if (keys.count(key) == 0) {
                keys.insert(key);
                for (int x : todo[key])
                    s.push(x);
            }

            for (auto [child, lock] : adj[node]) {
                if (keys.count(lock)) {
                    s.push(child);
                }
                else {
                    todo[lock].push_back(child);
                }
            }
        }

        if (count < minCount) {
            minCount = count;
            ans = { i };
        }
        else if (count == minCount) {
            ans.push_back(i);
        }
    }

    vi res(n);
    for (int x : ans)
        res[x] = 1;

	return res;
}

Compilation message (stderr)

keys.cpp: In function 'vi find_reachable(vi, vi, vi, vi)':
keys.cpp:117:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  117 |     for (int x : ans)
      |     ^~~
keys.cpp:120:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  120 |  return res;
      |  ^~~~~~

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