oj.uz

답안 #970835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
970835 2024-04-27T11:12:26 Z GrindMachine 열쇠 (IOI21_keys) C++17
100 / 100
 1061 ms 161444 KB 
#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> mp_siz(N);
vector<int> pending[N];

void merge_vectors(vector<int> &v1, vector<int> &v2){
	if(sz(v1) < sz(v2)) swap(v1,v2);
	trav(x,v2) v1.pb(x);
	v2.clear();
}

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);
				mp_siz[i]++;
			}
		}
	}

	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];

					merge_vectors(pending[u],pending[v]);
					merge_vectors(nodes[u],nodes[v]);

					if(sz(keys[u])+mp_siz[u] < sz(keys[v])+mp_siz[v]){
						swap(keys[u],keys[v]);
						swap(mp[u],mp[v]);
						swap(mp_siz[u],mp_siz[v]);
					}

					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);
								mp_siz[u]--;
							}
						}
					}

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

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

					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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 54360 KB Output is correct
2 Correct 13 ms 54360 KB Output is correct
3 Correct 13 ms 54364 KB Output is correct
4 Correct 13 ms 54364 KB Output is correct
5 Correct 14 ms 54364 KB Output is correct
6 Correct 13 ms 54236 KB Output is correct
7 Correct 14 ms 54340 KB Output is correct
8 Correct 15 ms 54364 KB Output is correct
9 Correct 13 ms 54364 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 54360 KB Output is correct
2 Correct 13 ms 54360 KB Output is correct
3 Correct 13 ms 54364 KB Output is correct
4 Correct 13 ms 54364 KB Output is correct
5 Correct 14 ms 54364 KB Output is correct
6 Correct 13 ms 54236 KB Output is correct
7 Correct 14 ms 54340 KB Output is correct
8 Correct 15 ms 54364 KB Output is correct
9 Correct 13 ms 54364 KB Output is correct
10 Correct 14 ms 54440 KB Output is correct
11 Correct 13 ms 54364 KB Output is correct
12 Correct 13 ms 54372 KB Output is correct
13 Correct 13 ms 54364 KB Output is correct
14 Correct 13 ms 54364 KB Output is correct
15 Correct 13 ms 54360 KB Output is correct
16 Correct 13 ms 54364 KB Output is correct
17 Correct 13 ms 54364 KB Output is correct
18 Correct 13 ms 54364 KB Output is correct
19 Correct 13 ms 54364 KB Output is correct
20 Correct 13 ms 54364 KB Output is correct
21 Correct 13 ms 54364 KB Output is correct
22 Correct 13 ms 54364 KB Output is correct
23 Correct 13 ms 54364 KB Output is correct
24 Correct 13 ms 54364 KB Output is correct
25 Correct 13 ms 54284 KB Output is correct
26 Correct 15 ms 54360 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 54360 KB Output is correct
2 Correct 13 ms 54360 KB Output is correct
3 Correct 13 ms 54364 KB Output is correct
4 Correct 13 ms 54364 KB Output is correct
5 Correct 14 ms 54364 KB Output is correct
6 Correct 13 ms 54236 KB Output is correct
7 Correct 14 ms 54340 KB Output is correct
8 Correct 15 ms 54364 KB Output is correct
9 Correct 13 ms 54364 KB Output is correct
10 Correct 14 ms 54440 KB Output is correct
11 Correct 13 ms 54364 KB Output is correct
12 Correct 13 ms 54372 KB Output is correct
13 Correct 13 ms 54364 KB Output is correct
14 Correct 13 ms 54364 KB Output is correct
15 Correct 13 ms 54360 KB Output is correct
16 Correct 13 ms 54364 KB Output is correct
17 Correct 13 ms 54364 KB Output is correct
18 Correct 13 ms 54364 KB Output is correct
19 Correct 13 ms 54364 KB Output is correct
20 Correct 13 ms 54364 KB Output is correct
21 Correct 13 ms 54364 KB Output is correct
22 Correct 13 ms 54364 KB Output is correct
23 Correct 13 ms 54364 KB Output is correct
24 Correct 13 ms 54364 KB Output is correct
25 Correct 13 ms 54284 KB Output is correct
26 Correct 15 ms 54360 KB Output is correct
27 Correct 15 ms 55132 KB Output is correct
28 Correct 14 ms 55132 KB Output is correct
29 Correct 15 ms 55144 KB Output is correct
30 Correct 14 ms 54620 KB Output is correct
31 Correct 13 ms 54620 KB Output is correct
32 Correct 15 ms 54364 KB Output is correct
33 Correct 15 ms 54620 KB Output is correct
34 Correct 14 ms 54620 KB Output is correct
35 Correct 14 ms 54620 KB Output is correct
36 Correct 16 ms 54876 KB Output is correct
37 Correct 16 ms 55244 KB Output is correct
38 Correct 18 ms 54876 KB Output is correct
39 Correct 17 ms 55132 KB Output is correct
40 Correct 14 ms 54616 KB Output is correct
41 Correct 15 ms 54876 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 54360 KB Output is correct
2 Correct 13 ms 54360 KB Output is correct
3 Correct 13 ms 54364 KB Output is correct
4 Correct 13 ms 54364 KB Output is correct
5 Correct 14 ms 54364 KB Output is correct
6 Correct 13 ms 54236 KB Output is correct
7 Correct 14 ms 54340 KB Output is correct
8 Correct 15 ms 54364 KB Output is correct
9 Correct 13 ms 54364 KB Output is correct
10 Correct 300 ms 130288 KB Output is correct
11 Correct 384 ms 130240 KB Output is correct
12 Correct 94 ms 74064 KB Output is correct
13 Correct 566 ms 149212 KB Output is correct
14 Correct 232 ms 127224 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 54360 KB Output is correct
2 Correct 13 ms 54360 KB Output is correct
3 Correct 13 ms 54364 KB Output is correct
4 Correct 13 ms 54364 KB Output is correct
5 Correct 14 ms 54364 KB Output is correct
6 Correct 13 ms 54236 KB Output is correct
7 Correct 14 ms 54340 KB Output is correct
8 Correct 15 ms 54364 KB Output is correct
9 Correct 13 ms 54364 KB Output is correct
10 Correct 14 ms 54440 KB Output is correct
11 Correct 13 ms 54364 KB Output is correct
12 Correct 13 ms 54372 KB Output is correct
13 Correct 13 ms 54364 KB Output is correct
14 Correct 13 ms 54364 KB Output is correct
15 Correct 13 ms 54360 KB Output is correct
16 Correct 13 ms 54364 KB Output is correct
17 Correct 13 ms 54364 KB Output is correct
18 Correct 13 ms 54364 KB Output is correct
19 Correct 13 ms 54364 KB Output is correct
20 Correct 13 ms 54364 KB Output is correct
21 Correct 13 ms 54364 KB Output is correct
22 Correct 13 ms 54364 KB Output is correct
23 Correct 13 ms 54364 KB Output is correct
24 Correct 13 ms 54364 KB Output is correct
25 Correct 13 ms 54284 KB Output is correct
26 Correct 15 ms 54360 KB Output is correct
27 Correct 15 ms 55132 KB Output is correct
28 Correct 14 ms 55132 KB Output is correct
29 Correct 15 ms 55144 KB Output is correct
30 Correct 14 ms 54620 KB Output is correct
31 Correct 13 ms 54620 KB Output is correct
32 Correct 15 ms 54364 KB Output is correct
33 Correct 15 ms 54620 KB Output is correct
34 Correct 14 ms 54620 KB Output is correct
35 Correct 14 ms 54620 KB Output is correct
36 Correct 16 ms 54876 KB Output is correct
37 Correct 16 ms 55244 KB Output is correct
38 Correct 18 ms 54876 KB Output is correct
39 Correct 17 ms 55132 KB Output is correct
40 Correct 14 ms 54616 KB Output is correct
41 Correct 15 ms 54876 KB Output is correct
42 Correct 300 ms 130288 KB Output is correct
43 Correct 384 ms 130240 KB Output is correct
44 Correct 94 ms 74064 KB Output is correct
45 Correct 566 ms 149212 KB Output is correct
46 Correct 232 ms 127224 KB Output is correct
47 Correct 13 ms 54360 KB Output is correct
48 Correct 13 ms 54364 KB Output is correct
49 Correct 14 ms 54364 KB Output is correct
50 Correct 242 ms 128612 KB Output is correct
51 Correct 230 ms 125740 KB Output is correct
52 Correct 250 ms 132692 KB Output is correct
53 Correct 260 ms 132744 KB Output is correct
54 Correct 251 ms 132600 KB Output is correct
55 Correct 260 ms 139216 KB Output is correct
56 Correct 403 ms 155304 KB Output is correct
57 Correct 285 ms 152764 KB Output is correct
58 Correct 459 ms 161444 KB Output is correct
59 Correct 1050 ms 151380 KB Output is correct
60 Correct 318 ms 142156 KB Output is correct
61 Correct 905 ms 143784 KB Output is correct
62 Correct 413 ms 135608 KB Output is correct
63 Correct 399 ms 136784 KB Output is correct
64 Correct 16 ms 55472 KB Output is correct
65 Correct 16 ms 55612 KB Output is correct
66 Correct 387 ms 135504 KB Output is correct
67 Correct 40 ms 61528 KB Output is correct
68 Correct 51 ms 66128 KB Output is correct
69 Correct 1059 ms 151216 KB Output is correct
70 Correct 86 ms 78164 KB Output is correct
71 Correct 238 ms 127064 KB Output is correct
72 Correct 1061 ms 151376 KB Output is correct
73 Correct 395 ms 135508 KB Output is correct