Submission #599940

#	Time	Username	Problem	Language	Result	Execution time	Memory
599940		Valaki2	Keys (IOI21_keys)	C++17	20 / 100	3100 ms	14224 KiB

keys

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

#define pb push_back

struct edge {
    int a, b, w;
    edge() : a(0), b(0), w(0) {}
    edge(int a_, int b_, int w_) :
        a(a_), b(b_), w(w_) {}
};

int n, m;
vector<int> key;
vector<edge> edges;
vector<int> p;

void solve() {
    for(int start = 0; start < n; start++) {
        vector<bool> have(n, 0);
        vector<bool> touched(n, 0);
        touched[start] = true;
        have[key[start]] = true;
        int cnt = 1;
        while(true) {
            bool is_new = false;
            for(edge e : edges) {
                if(have[e.w] && (touched[e.a] ^ touched[e.b])) {
                    int new_node = e.b;
                    if(touched[e.b]) {
                        new_node = e.a;
                    }
                    cnt++;
                    is_new = true;
                    touched[new_node] = true;
                    have[key[new_node]] = true;
                }
            }
            if(!is_new) {
                break;
            }
        }
        p[start] = cnt;
    }
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = r.size();
	m = c.size();
	key.assign(n, 0);
	for(int i = 0; i < n; i++) {
        key[i] = r[i];
	}
	edges.assign(m, edge());
	for(int i = 0; i < m; i++) {
        edges[i] = edge(u[i], v[i], c[i]);
	}
	p.assign(n, 0);
	solve();
	vector<int> ans(n, 0);
	int mini = *min_element(p.begin(), p.end());
	for(int i = 0; i < n; i++) {
        if(p[i] == mini) {
            ans[i] = 1;
        }
	}
	return ans;
}

/*
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2
*/

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