oj.uz

Submission #168397

# Submission time Handle Problem Language Result Execution time Memory
168397 2019-12-12T22:54:56 Z qkxwsm Bridges (APIO19_bridges) C++14
100 / 100
 2715 ms 8664 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 100013
#define MAGIC 820

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M, Q;
pii edge[MAXN];
int weight[MAXN], tmp[MAXN];
bitset<MAXN> typ;
pii quer[MAXN];
vector<pii> events;
bitset<MAXN> mentioned;
vi inds;
int dsu[MAXN], siz[MAXN];
vpi szs;
int ans[MAXN];

int get(int u)
{
	return (u == dsu[u] ? u : get(dsu[u]));
}
void merge(int u, int v, bool flag)
{
	u = get(u);
	v = get(v);
	if (u == v) return;
	if (siz[v] > siz[u]) swap(u, v);
	if (flag)
	{
		szs.PB({v, siz[v]});
		szs.PB({u, siz[u]});
	}
	dsu[v] = u;
	siz[u] += siz[v];
	siz[v] = 0;
}
void rollback()
{
	FORD(i, SZ(szs), 0)
	{
		dsu[szs[i].fi] = szs[i].fi;
		siz[szs[i].fi] = szs[i].se;
	}
	szs.clear();
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(12);
	cerr << fixed << setprecision(4);
	cin >> N >> M;
	FOR(i, 0, M)
	{
		int u, v, d;
		cin >> u >> v >> d;
		u--; v--;
		if (u > v) swap(u, v);
		edge[i] = {u, v};
		weight[i] = d;
	}
	cin >> Q;
	FOR(i, 0, Q)
	{
		int a, b, c;
		cin >> a >> b >> c; b--;
		if (a == 2)
		{
			typ[i] = true;
		}
		quer[i] = {b, c};
	}
	for (int i = 0; i < Q; i += MAGIC)
	{
		FOR(j, 0, N)
		{
			dsu[j] = j;
			siz[j] = 1;
		}
		mentioned.reset();
		inds.clear();
		events.clear();
		for (int j = i; j < i + MAGIC && j < Q; j++)
		{
			if (typ[j]) continue;
			mentioned[quer[j].fi] = true;
		}
		FOR(j, 0, M)
		{
			if (mentioned[j])
			{
				inds.PB(j);
			}
			else
			{
				events.PB({2 * weight[j] + 1, j});
			}
		}
		for (int j = i; j < i + MAGIC && j < Q; j++)
		{
			if (!typ[j]) continue;
			events.PB({2 * quer[j].se, j});
		}
		sort(ALL(events), greater<pii>());
		for (auto e : events)
		{
			int idx = e.se;
			if (e.fi & 1)
			{
				merge(edge[idx].fi, edge[idx].se, 0);
			}
			else
			{
				for (int x : inds)
				{
					tmp[x] = weight[x];
				}
				FOR(j, i, idx)
				{
					if (typ[j]) continue;
					tmp[quer[j].fi] = quer[j].se;
				}
				for (int x : inds)
				{
					if (tmp[x] >= quer[idx].se)
					{
						merge(edge[x].fi, edge[x].se, 1);
					}
				}
				int u = quer[idx].fi;
				u = get(u);
				ans[idx] = siz[u];
				rollback();
			}
		}
		for (int j = i; j < i + MAGIC && j < Q; j++)
		{
			if (typ[j]) continue;
			weight[quer[j].fi] = quer[j].se;
		}
	}
	FOR(i, 0, Q)
	{
		if (!typ[i]) continue;
		cout << ans[i] << '\n';
	}
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 30 ms 760 KB Output is correct
4 Correct 12 ms 632 KB Output is correct
5 Correct 16 ms 632 KB Output is correct
6 Correct 15 ms 760 KB Output is correct
7 Correct 20 ms 760 KB Output is correct
8 Correct 19 ms 760 KB Output is correct
9 Correct 25 ms 632 KB Output is correct
10 Correct 20 ms 632 KB Output is correct
11 Correct 20 ms 764 KB Output is correct
12 Correct 22 ms 760 KB Output is correct
13 Correct 25 ms 760 KB Output is correct
14 Correct 24 ms 760 KB Output is correct
15 Correct 21 ms 632 KB Output is correct
16 Correct 22 ms 632 KB Output is correct
17 Correct 21 ms 632 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1738 ms 3800 KB Output is correct
2 Correct 1747 ms 3772 KB Output is correct
3 Correct 1670 ms 3816 KB Output is correct
4 Correct 1682 ms 3780 KB Output is correct
5 Correct 1711 ms 3876 KB Output is correct
6 Correct 2431 ms 3956 KB Output is correct
7 Correct 2422 ms 3956 KB Output is correct
8 Correct 2437 ms 3988 KB Output is correct
9 Correct 99 ms 1912 KB Output is correct
10 Correct 1454 ms 3732 KB Output is correct
11 Correct 1467 ms 3628 KB Output is correct
12 Correct 1436 ms 4172 KB Output is correct
13 Correct 1578 ms 3480 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1328 ms 3276 KB Output is correct
2 Correct 886 ms 2424 KB Output is correct
3 Correct 1514 ms 3368 KB Output is correct
4 Correct 1291 ms 3188 KB Output is correct
5 Correct 99 ms 1912 KB Output is correct
6 Correct 1446 ms 3064 KB Output is correct
7 Correct 1218 ms 3216 KB Output is correct
8 Correct 1092 ms 3004 KB Output is correct
9 Correct 902 ms 3152 KB Output is correct
10 Correct 854 ms 3232 KB Output is correct
11 Correct 946 ms 3008 KB Output is correct
12 Correct 888 ms 3076 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2222 ms 4668 KB Output is correct
2 Correct 100 ms 1912 KB Output is correct
3 Correct 223 ms 2932 KB Output is correct
4 Correct 257 ms 2932 KB Output is correct
5 Correct 2087 ms 4852 KB Output is correct
6 Correct 2100 ms 4820 KB Output is correct
7 Correct 2069 ms 4884 KB Output is correct
8 Correct 1098 ms 3444 KB Output is correct
9 Correct 1148 ms 3444 KB Output is correct
10 Correct 1086 ms 3700 KB Output is correct
11 Correct 1652 ms 4144 KB Output is correct
12 Correct 1652 ms 4020 KB Output is correct
13 Correct 1641 ms 4276 KB Output is correct
14 Correct 1834 ms 4724 KB Output is correct
15 Correct 1969 ms 4692 KB Output is correct
16 Correct 2149 ms 4788 KB Output is correct
17 Correct 2108 ms 4824 KB Output is correct
18 Correct 2124 ms 4724 KB Output is correct
19 Correct 2136 ms 4788 KB Output is correct
20 Correct 1768 ms 4644 KB Output is correct
21 Correct 1771 ms 4636 KB Output is correct
22 Correct 2031 ms 4752 KB Output is correct
23 Correct 1860 ms 4428 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1738 ms 3800 KB Output is correct
2 Correct 1747 ms 3772 KB Output is correct
3 Correct 1670 ms 3816 KB Output is correct
4 Correct 1682 ms 3780 KB Output is correct
5 Correct 1711 ms 3876 KB Output is correct
6 Correct 2431 ms 3956 KB Output is correct
7 Correct 2422 ms 3956 KB Output is correct
8 Correct 2437 ms 3988 KB Output is correct
9 Correct 99 ms 1912 KB Output is correct
10 Correct 1454 ms 3732 KB Output is correct
11 Correct 1467 ms 3628 KB Output is correct
12 Correct 1436 ms 4172 KB Output is correct
13 Correct 1578 ms 3480 KB Output is correct
14 Correct 1328 ms 3276 KB Output is correct
15 Correct 886 ms 2424 KB Output is correct
16 Correct 1514 ms 3368 KB Output is correct
17 Correct 1291 ms 3188 KB Output is correct
18 Correct 99 ms 1912 KB Output is correct
19 Correct 1446 ms 3064 KB Output is correct
20 Correct 1218 ms 3216 KB Output is correct
21 Correct 1092 ms 3004 KB Output is correct
22 Correct 902 ms 3152 KB Output is correct
23 Correct 854 ms 3232 KB Output is correct
24 Correct 946 ms 3008 KB Output is correct
25 Correct 888 ms 3076 KB Output is correct
26 Correct 1749 ms 3744 KB Output is correct
27 Correct 2176 ms 3828 KB Output is correct
28 Correct 1875 ms 3824 KB Output is correct
29 Correct 1437 ms 3788 KB Output is correct
30 Correct 2106 ms 3724 KB Output is correct
31 Correct 2157 ms 3704 KB Output is correct
32 Correct 2178 ms 3792 KB Output is correct
33 Correct 1865 ms 3696 KB Output is correct
34 Correct 1861 ms 3828 KB Output is correct
35 Correct 1861 ms 3800 KB Output is correct
36 Correct 1487 ms 3764 KB Output is correct
37 Correct 1489 ms 3604 KB Output is correct
38 Correct 1457 ms 3988 KB Output is correct
39 Correct 1239 ms 3876 KB Output is correct
40 Correct 1235 ms 3920 KB Output is correct
41 Correct 1242 ms 3704 KB Output is correct
42 Correct 1216 ms 3664 KB Output is correct
43 Correct 1231 ms 3588 KB Output is correct
44 Correct 1221 ms 3704 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 30 ms 760 KB Output is correct
4 Correct 12 ms 632 KB Output is correct
5 Correct 16 ms 632 KB Output is correct
6 Correct 15 ms 760 KB Output is correct
7 Correct 20 ms 760 KB Output is correct
8 Correct 19 ms 760 KB Output is correct
9 Correct 25 ms 632 KB Output is correct
10 Correct 20 ms 632 KB Output is correct
11 Correct 20 ms 764 KB Output is correct
12 Correct 22 ms 760 KB Output is correct
13 Correct 25 ms 760 KB Output is correct
14 Correct 24 ms 760 KB Output is correct
15 Correct 21 ms 632 KB Output is correct
16 Correct 22 ms 632 KB Output is correct
17 Correct 21 ms 632 KB Output is correct
18 Correct 1738 ms 3800 KB Output is correct
19 Correct 1747 ms 3772 KB Output is correct
20 Correct 1670 ms 3816 KB Output is correct
21 Correct 1682 ms 3780 KB Output is correct
22 Correct 1711 ms 3876 KB Output is correct
23 Correct 2431 ms 3956 KB Output is correct
24 Correct 2422 ms 3956 KB Output is correct
25 Correct 2437 ms 3988 KB Output is correct
26 Correct 99 ms 1912 KB Output is correct
27 Correct 1454 ms 3732 KB Output is correct
28 Correct 1467 ms 3628 KB Output is correct
29 Correct 1436 ms 4172 KB Output is correct
30 Correct 1578 ms 3480 KB Output is correct
31 Correct 1328 ms 3276 KB Output is correct
32 Correct 886 ms 2424 KB Output is correct
33 Correct 1514 ms 3368 KB Output is correct
34 Correct 1291 ms 3188 KB Output is correct
35 Correct 99 ms 1912 KB Output is correct
36 Correct 1446 ms 3064 KB Output is correct
37 Correct 1218 ms 3216 KB Output is correct
38 Correct 1092 ms 3004 KB Output is correct
39 Correct 902 ms 3152 KB Output is correct
40 Correct 854 ms 3232 KB Output is correct
41 Correct 946 ms 3008 KB Output is correct
42 Correct 888 ms 3076 KB Output is correct
43 Correct 2222 ms 4668 KB Output is correct
44 Correct 100 ms 1912 KB Output is correct
45 Correct 223 ms 2932 KB Output is correct
46 Correct 257 ms 2932 KB Output is correct
47 Correct 2087 ms 4852 KB Output is correct
48 Correct 2100 ms 4820 KB Output is correct
49 Correct 2069 ms 4884 KB Output is correct
50 Correct 1098 ms 3444 KB Output is correct
51 Correct 1148 ms 3444 KB Output is correct
52 Correct 1086 ms 3700 KB Output is correct
53 Correct 1652 ms 4144 KB Output is correct
54 Correct 1652 ms 4020 KB Output is correct
55 Correct 1641 ms 4276 KB Output is correct
56 Correct 1834 ms 4724 KB Output is correct
57 Correct 1969 ms 4692 KB Output is correct
58 Correct 2149 ms 4788 KB Output is correct
59 Correct 2108 ms 4824 KB Output is correct
60 Correct 2124 ms 4724 KB Output is correct
61 Correct 2136 ms 4788 KB Output is correct
62 Correct 1768 ms 4644 KB Output is correct
63 Correct 1771 ms 4636 KB Output is correct
64 Correct 2031 ms 4752 KB Output is correct
65 Correct 1860 ms 4428 KB Output is correct
66 Correct 1749 ms 3744 KB Output is correct
67 Correct 2176 ms 3828 KB Output is correct
68 Correct 1875 ms 3824 KB Output is correct
69 Correct 1437 ms 3788 KB Output is correct
70 Correct 2106 ms 3724 KB Output is correct
71 Correct 2157 ms 3704 KB Output is correct
72 Correct 2178 ms 3792 KB Output is correct
73 Correct 1865 ms 3696 KB Output is correct
74 Correct 1861 ms 3828 KB Output is correct
75 Correct 1861 ms 3800 KB Output is correct
76 Correct 1487 ms 3764 KB Output is correct
77 Correct 1489 ms 3604 KB Output is correct
78 Correct 1457 ms 3988 KB Output is correct
79 Correct 1239 ms 3876 KB Output is correct
80 Correct 1235 ms 3920 KB Output is correct
81 Correct 1242 ms 3704 KB Output is correct
82 Correct 1216 ms 3664 KB Output is correct
83 Correct 1231 ms 3588 KB Output is correct
84 Correct 1221 ms 3704 KB Output is correct
85 Correct 2663 ms 4908 KB Output is correct
86 Correct 250 ms 3184 KB Output is correct
87 Correct 270 ms 3184 KB Output is correct
88 Correct 2466 ms 5224 KB Output is correct
89 Correct 2666 ms 8444 KB Output is correct
90 Correct 2508 ms 6956 KB Output is correct
91 Correct 1921 ms 6176 KB Output is correct
92 Correct 1880 ms 6300 KB Output is correct
93 Correct 2715 ms 6280 KB Output is correct
94 Correct 2173 ms 7384 KB Output is correct
95 Correct 2263 ms 7332 KB Output is correct
96 Correct 2190 ms 7328 KB Output is correct
97 Correct 2159 ms 7160 KB Output is correct
98 Correct 2220 ms 6904 KB Output is correct
99 Correct 2565 ms 8664 KB Output is correct
100 Correct 2556 ms 8560 KB Output is correct
101 Correct 2710 ms 8576 KB Output is correct
102 Correct 2686 ms 8580 KB Output is correct
103 Correct 2371 ms 7796 KB Output is correct
104 Correct 2319 ms 7668 KB Output is correct
105 Correct 2024 ms 7460 KB Output is correct
106 Correct 1722 ms 7056 KB Output is correct
107 Correct 1910 ms 7788 KB Output is correct
108 Correct 2427 ms 8208 KB Output is correct
109 Correct 2253 ms 6360 KB Output is correct