Submission #559153

#	Time	Username	Problem	Language	Result	Execution time	Memory
559153		hoanghq2004	Keys (IOI21_keys)	C++17	0 / 100	1 ms	404 KiB

keys

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "keys.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2010;

int n;
vector <int> s[N];
int vis[N], had[N];
vector <pair <int, int>> g[N];

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();
	int m = c.size();
	for (int i = 0; i < m; ++i) {
        g[u[i]].push_back({v[i], c[i]});
        g[v[i]].push_back({u[i], c[i]});
	}
    auto solve = [&](int S) {
        memset(had, 0, sizeof(had));
        memset(vis, 0, sizeof(vis));
        vis[S] = 1;
        queue <int> q;
        q.push(S);
        while (q.size()) {
            int u = q.front();
            q.pop();
            if (had[r[u]] == 0) {
                had[r[u]] = 1;
                for (auto v: s[r[u]]) {
                    if (vis[v]) continue;
                    vis[v] = 1;
                    q.push(v);
                }
            }
            for (auto [v, w]: g[u]) {
                if (vis[v]) continue;
                if (had[w]) {
                    vis[v] = 1;
                    q.push(v);
                    continue;
                }
                s[w].push_back(v);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) ans += vis[i];
        return ans;
    };
    vector <int> ans(n);
    int best = 1e9;
    for (int i = 0; i < n; ++i) best = min(best, solve(i));
    for (int i = 0; i < n; ++i) if (best == solve(i)) ans[i] = 1;
	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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33