Submission #930287

#	Time	Username	Problem	Language	Result	Execution time	Memory
930287		Kanon	Keys (IOI21_keys)	C++17	100 / 100	1078 ms	129084 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 = 3e5 + 10;
 
int n;
int par[N], sz[N];
map <int, vector <int> > g[N];
set <int> key[N];
vector <int> to[N];
 
int Find(int u) {
    return (u == par[u] ? u : par[u] = Find(par[u]));
}
 
void Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return;
    if (key[u].size() + to[u].size() < key[v].size() + to[v].size()) {
      swap(key[u], key[v]);
      swap(to[u], to[v]); 
      swap(g[u], g[v]);
    } 
    par[v] = u;
    sz[u] += sz[v];
    for (auto w: to[v]) to[u].push_back(w);
    to[v].clear();
    for (auto c: key[v]) {
        if (g[u].find(c) != g[u].end()) {
            for (auto w: g[u][c]) to[u].push_back(w);
            g[u].erase(c);
        }
    }
    for (auto [c, _]: g[v]) {
        if (key[u].find(c) != key[u].end()) {
            for (auto w: g[v][c]) to[u].push_back(w);
        } else for (auto w: g[v][c]) g[u][c].push_back(w);
    }
    g[v].clear();
    key[u].insert(key[v].begin(), key[v].end());
    key[v].clear();
}
 
int bad[N];
int state[N];
int last[N];
 
void dfs(int u) {
    state[u] = 0;
    while (1) {
        u = Find(u);
        if (to[u].empty()) break;
        int v = to[u].back();
        to[u].pop_back();
        v = Find(v);
        if (u == v) continue;
        if (state[v] == -1) {
            last[v] = u;
            dfs(v);
            if (Find(u) != Find(v)) bad[u] = 1;
        } else if (state[v] == 0) {
            int w = u;
            while (1) {
                if (Find(w) == Find(v)) break;
                Union(v, w);
                w = last[w];
            }
        } else bad[u] = 1;
    }
    state[u] = 1;
}
 
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();
	auto add_edge = [&](int u, int v, int c) {
        if (r[u] == c) to[u].push_back(v);
        else g[u][c].push_back(v);
	};
	for (int i = 0; i < m; ++i) {
        add_edge(u[i], v[i], c[i]);
        add_edge(v[i], u[i], c[i]);
	}
	for (int i = 0; i < n; ++i) par[i] = i, sz[i] = 1, key[i].insert(r[i]);
 
	memset(state, -1, sizeof(state));
    for (int i = 0; i < n; ++i) if (state[i] == -1) dfs(i);
	for (int i = 0; i < n; ++i) {
      if (i == Find(i)) assert(state[i] == 1);
      else assert(state[i] == 0);
    }
    for (int i = 0; i < n; ++i) if (bad[i]) bad[Find(i)] = 1;
    vector <int> flag(n, 0);
    int ans = 1e9;
    for (int i = 0; i < n; ++i)
        if (i == Find(i) && !bad[i]) ans = min(ans, sz[i]);
    for (int i = 0; i < n; ++i)
        if (!bad[Find(i)] && sz[Find(i)] == ans) flag[i] = 1;
    return flag;
}
 
//int main() {
//    freopen("IOI21_keys.inp", "r", stdin);
////    freopen("IOI21_keys.out", "w", stdout);
//    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: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33