oj.uz

Submission #568020

# Submission time Handle Problem Language Result Execution time Memory
568020 2022-05-24T13:58:25 Z Zanite Swapping Cities (APIO20_swap) C++17
30 / 100
 1160 ms 43964 KB 
// You can't change other people; you can only change yourself.

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

#include "swap.h"

// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;

// Data types
using i8	= __int128;
using ll	= long long;
using si	= short int;
using ld	= long double;

// Pairs
using pi8	= pair<i8, i8>;
using pll	= pair<ll, ll>;
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pld	= pair<ld, ld>;
#define fi first
#define se second

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

// Quick macro functions
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

// Constants
const ll ModA	= 998244353;
const ll ModC	= 1e9 + 7;
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;

struct OnlineDSU {
	int n;
	vector<vector<pii>> par, sz, degree, maxdegree, edgecount;

	OnlineDSU(int _n) {
		n = _n;
		for (int i = 0; i < n; i++) {
			par.push_back({{0, i}});
		}
		sz.assign(n, {{0, 1}});
		degree.assign(n, {{0, 0}});
		maxdegree.assign(n, {{0, 0}});
		edgecount.assign(n, {{0, 0}});
	}

	void insert(vector<pii> &v, int val, int t) {
		if (v.back().se == val) {return;}
		if (v.back().fi == t) {
			v.back().se = val;
		} else {
			v.push_back({t, val});
		}
	}

	int query(vector<pii> &v, int t) {
		pii search = {t+1, -iINF};
		auto it = upper_bound(v.begin(), v.end(), search);
		it--;
		return it->second;
	}

	int parent_latest(int x) {return par[x].back().se;}
	int size_latest(int x) {return sz[x].back().se;}
	int degree_latest(int x) {return degree[x].back().se;}
	int maxdegree_latest(int x) {return maxdegree[x].back().se;}
	int edgecount_latest(int x) {return edgecount[x].back().se;}

	int get_degree(int x, int t) {return query(degree[x], t);}
	int get_maxdegree(int x, int t) {return query(maxdegree[x], t);}
	int get_edgecount(int x, int t) {return query(edgecount[x], t);}
	int get_size(int x, int t) {return query(sz[x], t);}

	int rep_latest(int x, int t) {
		if (x == parent_latest(x)) {return x;}
		insert(par[x], rep_latest(parent_latest(x), t), t);
		return parent_latest(x);
	}

	int rep(int x, int t) {
		int p = query(par[x], t);
		if (x == p) {return x;}
		return rep(p, t);
	}

	void join_latest(int u, int v, int t) {
		insert(degree[u], degree_latest(u)+1, t);
		insert(degree[v], degree_latest(v)+1, t);

		int x = rep_latest(u, t), y = rep_latest(v, t);
		if (x != y) {
			if (size_latest(x) < size_latest(y)) {swap(x, y);}

			insert(par[y], x, t);
			insert(sz[x], size_latest(x) + size_latest(y), t);

			int mx = maxdegree_latest(x), my = maxdegree_latest(y);
			insert(maxdegree[x], max(max(mx, my), max(degree_latest(u), degree_latest(v))), t);

			int e = edgecount_latest(x);
			insert(edgecount[x], e+1, t);
		} else {
			insert(maxdegree[x], max(degree_latest(u), degree_latest(v)), t);
			int e = edgecount_latest(x);
			insert(edgecount[x], e+1, t);
		}
	}

	bool check(int u, int v, int t) {
		int x = rep(u, t), y = rep(v, t);
		return (x == y);
	}
};

void print(vector<vector<pii>> &v) {
	for (int i = 0; i < v.size(); i++) {
		cout << i << ": ";
		for (auto j : v[i]) {
			cout << "{" << j.fi << ", " << j.se << "} ";
		}
		cout << '\n';
	}
	cout << '\n';
}

using Edge	= pair<int, pii>;

OnlineDSU *D;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	vector<Edge> E;
	for (int i = 0; i < M; i++) {
		E.push_back({W[i], {U[i], V[i]}});
	}
	sort(E.begin(), E.end());

	D = new OnlineDSU(N);
	for (auto x : E) {
		D->join_latest(x.se.fi, x.se.se, x.fi);
		//printf("%d: %d %d\n", x.fi, x.se.fi, x.se.se);
	}

	/*
	cout << "par\n";
	print(D->par);
	cout << "sz\n";
	print(D->sz);
	cout << "degree\n";
	print(D->degree);
	cout << "maxdegree\n";
	print(D->maxdegree);
	cout << "edgecount\n";
	print(D->edgecount);
	*/
}

const int MAX = 1e9;

int getMinimumFuelCapacity(int X, int Y) {
	int L = 1, R = MAX, ans = -1;
	while (L <= R) {
		int M = (L + R) >> 1;

		bool pos = 1;
		if (!D->check(X, Y, M)) {
			pos = 0;
		} else {
			int R = D->rep(X, M);
			if (D->get_maxdegree(R, M) > 2 || D->get_size(R, M) == D->get_edgecount(R, M)) {
				pos = 1;
			} else {
				pos = 0;
			}
		}

		if (pos) {
			R = M - 1;
			ans = M;
		} else {
			L = M + 1;
		}
	}
	return ans;
}

//int main() {}

Compilation message

swap.cpp: In function 'void print(std::vector<std::vector<std::pair<int, int> > >&)':
swap.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 708 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 180 ms 31520 KB Output is correct
10 Correct 251 ms 38516 KB Output is correct
11 Correct 206 ms 37896 KB Output is correct
12 Correct 247 ms 40088 KB Output is correct
13 Correct 164 ms 37796 KB Output is correct
14 Correct 240 ms 31804 KB Output is correct
15 Correct 927 ms 42620 KB Output is correct
16 Correct 955 ms 41604 KB Output is correct
17 Correct 959 ms 43964 KB Output is correct
18 Correct 682 ms 41280 KB Output is correct
19 Incorrect 492 ms 10376 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 556 ms 40136 KB Output is correct
4 Correct 517 ms 39684 KB Output is correct
5 Correct 561 ms 38552 KB Output is correct
6 Correct 555 ms 39512 KB Output is correct
7 Correct 567 ms 39200 KB Output is correct
8 Correct 536 ms 37744 KB Output is correct
9 Correct 555 ms 38888 KB Output is correct
10 Correct 542 ms 37352 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 708 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 3 ms 676 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Incorrect 2 ms 596 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 708 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 180 ms 31520 KB Output is correct
11 Correct 251 ms 38516 KB Output is correct
12 Correct 206 ms 37896 KB Output is correct
13 Correct 247 ms 40088 KB Output is correct
14 Correct 164 ms 37796 KB Output is correct
15 Correct 2 ms 692 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 3 ms 676 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 724 KB Output is correct
21 Correct 2 ms 696 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Incorrect 2 ms 596 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 708 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 180 ms 31520 KB Output is correct
10 Correct 251 ms 38516 KB Output is correct
11 Correct 206 ms 37896 KB Output is correct
12 Correct 247 ms 40088 KB Output is correct
13 Correct 164 ms 37796 KB Output is correct
14 Correct 240 ms 31804 KB Output is correct
15 Correct 927 ms 42620 KB Output is correct
16 Correct 955 ms 41604 KB Output is correct
17 Correct 959 ms 43964 KB Output is correct
18 Correct 682 ms 41280 KB Output is correct
19 Correct 556 ms 40136 KB Output is correct
20 Correct 517 ms 39684 KB Output is correct
21 Correct 561 ms 38552 KB Output is correct
22 Correct 555 ms 39512 KB Output is correct
23 Correct 567 ms 39200 KB Output is correct
24 Correct 536 ms 37744 KB Output is correct
25 Correct 555 ms 38888 KB Output is correct
26 Correct 542 ms 37352 KB Output is correct
27 Correct 2 ms 692 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 3 ms 676 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 2 ms 724 KB Output is correct
33 Correct 2 ms 696 KB Output is correct
34 Correct 1 ms 596 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 20 ms 5512 KB Output is correct
37 Correct 243 ms 39372 KB Output is correct
38 Correct 237 ms 39332 KB Output is correct
39 Correct 270 ms 39516 KB Output is correct
40 Correct 248 ms 38796 KB Output is correct
41 Correct 238 ms 38460 KB Output is correct
42 Correct 200 ms 35044 KB Output is correct
43 Correct 267 ms 39688 KB Output is correct
44 Correct 232 ms 39496 KB Output is correct
45 Correct 172 ms 36556 KB Output is correct
46 Correct 251 ms 38996 KB Output is correct
47 Correct 76 ms 5464 KB Output is correct
48 Correct 1160 ms 41760 KB Output is correct
49 Correct 1113 ms 41764 KB Output is correct
50 Correct 1072 ms 41828 KB Output is correct
51 Correct 996 ms 41504 KB Output is correct
52 Correct 976 ms 39140 KB Output is correct
53 Correct 694 ms 29836 KB Output is correct
54 Correct 1093 ms 42240 KB Output is correct
55 Correct 1122 ms 41768 KB Output is correct
56 Correct 488 ms 39504 KB Output is correct
57 Correct 779 ms 41624 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 708 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 180 ms 31520 KB Output is correct
11 Correct 251 ms 38516 KB Output is correct
12 Correct 206 ms 37896 KB Output is correct
13 Correct 247 ms 40088 KB Output is correct
14 Correct 164 ms 37796 KB Output is correct
15 Correct 240 ms 31804 KB Output is correct
16 Correct 927 ms 42620 KB Output is correct
17 Correct 955 ms 41604 KB Output is correct
18 Correct 959 ms 43964 KB Output is correct
19 Correct 682 ms 41280 KB Output is correct
20 Correct 556 ms 40136 KB Output is correct
21 Correct 517 ms 39684 KB Output is correct
22 Correct 561 ms 38552 KB Output is correct
23 Correct 555 ms 39512 KB Output is correct
24 Correct 567 ms 39200 KB Output is correct
25 Correct 536 ms 37744 KB Output is correct
26 Correct 555 ms 38888 KB Output is correct
27 Correct 542 ms 37352 KB Output is correct
28 Correct 2 ms 692 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 3 ms 676 KB Output is correct
31 Correct 2 ms 596 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 2 ms 724 KB Output is correct
34 Correct 2 ms 696 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 2 ms 596 KB Output is correct
37 Correct 20 ms 5512 KB Output is correct
38 Correct 243 ms 39372 KB Output is correct
39 Correct 237 ms 39332 KB Output is correct
40 Correct 270 ms 39516 KB Output is correct
41 Correct 248 ms 38796 KB Output is correct
42 Correct 238 ms 38460 KB Output is correct
43 Correct 200 ms 35044 KB Output is correct
44 Correct 267 ms 39688 KB Output is correct
45 Correct 232 ms 39496 KB Output is correct
46 Correct 172 ms 36556 KB Output is correct
47 Correct 251 ms 38996 KB Output is correct
48 Correct 76 ms 5464 KB Output is correct
49 Correct 1160 ms 41760 KB Output is correct
50 Correct 1113 ms 41764 KB Output is correct
51 Correct 1072 ms 41828 KB Output is correct
52 Correct 996 ms 41504 KB Output is correct
53 Correct 976 ms 39140 KB Output is correct
54 Correct 694 ms 29836 KB Output is correct
55 Correct 1093 ms 42240 KB Output is correct
56 Correct 1122 ms 41768 KB Output is correct
57 Correct 488 ms 39504 KB Output is correct
58 Correct 779 ms 41624 KB Output is correct
59 Incorrect 492 ms 10376 KB Output isn't correct
60 Halted 0 ms 0 KB -