Submission #1242826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242826		santi3223	Keys (IOI21_keys)	C++20	9 / 100	89 ms	22340 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < (ll)cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;

vector<vl> conexiones;
vb visited;
ll c = 0;
void dfs(int cur){
	if(visited[cur]){
		return;
	}
	visited[cur] = true;
	c++;
	for(auto &p : conexiones[cur]){
		dfs(p);
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> C) {
	ll n = r.size();
	vector<int> calc(n, -1);
	int minn = n;
	ll m = u.size();
	conexiones = vector<vl>(n);
	ff(i, 0, m){
		conexiones[u[i]].pb(v[i]);
		conexiones[v[i]].pb(u[i]);
	}
	ff(i, 0, n){
		if(r[i] == 0){
			if(calc[i] != -1){
				//cout << "I " << i << ed;
				continue;
			}
			visited = vb(n, false);
			c = 0;
			dfs(i);
			ff(id, 0, n){
				if(visited[id]){
					calc[id] = c;
				}
			}
			calc[i] = c;
		}
		else{
			calc[i] = 1;
		}
		minn = min(minn, calc[i]);
	}
	vector<int> ans(n, 0);
	ff(i, 0, n){
		if(calc[i] == minn){
			ans[i] = 1;
		}
	}
	/*ff(i, 0, n){
		cout << calc[i] << " ";
	}
	cout << ed;*/
	return ans;
}
/*
int main() {
    int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    std::vector<int> r(n), u(m), v(m), C(m);
    for(int i=0; i<n; i++) {
        assert(1 == scanf("%d", &r[i]));
    }
    for(int i=0; i<m; i++) {
        assert(3 == scanf("%d %d %d", &u[i], &v[i], &C[i]));
    }
    fclose(stdin);

    std::vector<int> ans = find_reachable(r, u, v, C);

    for (int i = 0; i < (int) ans.size(); ++i) {
        if(i) putchar(' ');
        putchar(ans[i]+'0');
    }
    printf("\n");
    return 0;
}
*/

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