Submission #435082

#	Time	Username	Problem	Language	Result	Execution time	Memory
435082		Ozy	Keys (IOI21_keys)	C++17	9 / 100	128 ms	17996 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 2000

int n,m,MIN;
int visitados[MAX+2], active[MAX+2];
vector<int> room,res;
map<int, int> llaves;
vector<int> hijos[MAX+2];
vector<pair<int ,int> > aristas[MAX+2];

void DFS(int pos, int glob) {

    visitados[pos] = glob;
    res[glob]++;
    if (llaves[room[pos]] == 0) {
        llaves[room[pos]] = 1;
        if(active[room[pos]] < glob)
        {
            active[room[pos]] = glob;
            for (auto act : aristas[room[pos]]) {
                hijos[act.first].push_back(act.second);
                hijos[act.second].push_back(act.first);
            }
        }
    }

    for (auto h : hijos[pos]) if (visitados[h] != glob) DFS(h,glob);

}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {

	n = r.size();
	m = u.size();
	res.resize(n,0);
	room.resize(n,0);

	rep(i,0,n-1) room[i] = r[i];
	rep(i,0,n-1) visitados[i] = -1, active[i] = -1;
	rep(i,0,m-1) aristas[ c[i] ].push_back({v[i], u[i]});

	MIN = MAX*2;
	rep(i,0,n-1) {
        llaves.clear();
        rep(j,0,n-1) hijos[j].clear();
        DFS(i,i);
        if (res[i] < MIN) MIN = res[i];
	}

	rep(i,0,n-1) if (res[i] == MIN) res[i] = 1;
	else res[i] = 0;

	return res;
}

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