Submission #970829

#	Time	Username	Problem	Language	Result	Execution time	Memory
970829		GrindMachine	Keys (IOI21_keys)	C++17	100 / 100	1102 ms	167100 KiB

keys

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/92083?#comment-807712

*/

const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

struct DSU {
    vector<int> par, rankk, siz;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        siz[u] = 1;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        siz[u] += siz[v];
    }
};

vector<pii> adj[N];
vector<int> node_id(N), up(N);
vector<int> siz(N);
vector<int> nodes[N];
set<int> keys[N];
map<int,vector<int>> mp[N];
vector<int> pending[N];

std::vector<int> find_reachable(std::vector<int> a, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	int n = sz(a), m = sz(U);
	rep(i,m){
		int u = U[i], v = V[i], w = W[i];
		adj[u].pb({v,w}), adj[v].pb({u,w});
	}

	DSU dsu(n);
	set<pii> st;
	rep(i,n) st.insert({1,i});

	rep(i,n){
		node_id[i] = i;
		up[i] = i;
		siz[i] = 1;
		nodes[i].pb(i);
		keys[i].insert(a[i]);
		for(auto [v,key] : adj[i]){
			if(key == a[i]){
				pending[i].pb(v);
			}
			else{
				mp[i][key].pb(v);
			}
		}
	}

	vector<int> ans(n);
	int mn_reach = inf1;

	while(!st.empty()){
		auto [sizu,u] = *st.begin();
		if(sizu > mn_reach) break;

		st.erase(st.begin());
		bool done = false;

		while(!pending[u].empty()){
			int v = pending[u].back();
			pending[u].pop_back();
			v = node_id[v];
			if(node_id[u] == node_id[v]) conts;
			
			done = true;

			if(!dsu.same(u,v)){
				// par
				up[u] = v;
				dsu.merge(u,v);
			}
			else{
				// cyc
				vector<int> cyc_nodes;
				while(v != u){
					cyc_nodes.pb(v);
					v = node_id[up[v]];
				}

				trav(v,cyc_nodes){
					node_id[v] = u;
					st.erase({siz[v],v});
					siz[u] += siz[v];
					trav(x,pending[v]){
						pending[u].pb(x);
					}
					pending[v].clear();

					trav(x,nodes[v]){
						nodes[u].pb(x);
					}
					nodes[v].clear();

					trav(key,keys[v]){
						if(keys[u].count(key)) conts;
						keys[u].insert(key);
						if(mp[u].count(key)){
							auto &curr = mp[u][key];
							while(!curr.empty()){
								int w = curr.back();
								curr.pop_back();
								pending[u].pb(w);
							}
						}
					}

					for(auto [key,adj_nodes] : mp[v]){
						auto &curr = mp[u][key];
						trav(w,adj_nodes){
							curr.pb(w);
						}

						if(keys[u].count(key)){
							while(!curr.empty()){
								int w = curr.back();
								curr.pop_back();
								pending[u].pb(w);
							}
						}
					}

					keys[v].clear();
					mp[v].clear();
				}

				st.insert({siz[u],u});
			}

			break;
		}

		if(!done){
			if(sizu < mn_reach){
				mn_reach = sizu;
			}
			
			assert(sizu == mn_reach);

			trav(x,nodes[u]){
				ans[x] = 1;
			}
		}
	}

	return ans;
}

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