oj.uz

답안 #721490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721490 2023-04-11T02:33:54 Z LittleCube 다리 (APIO19_bridges) C++17
100 / 100
 2884 ms 140968 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const int B = 550;
int N, M, Q, u[100005], v[100005], d[100005], nd[100005], ans[100005], dsu[50005], rk[50005], vis[100005];
vector<pii> ops;

int find(int k)
{
	return k == dsu[k] ? k : find(dsu[k]);
}

void merge(int x, int y)
{
	x = find(x), y = find(y);
	if(x == y)
		return;
	if(rk[x] < rk[y])
		merge(y, x);
	else
	{
		dsu[y] = x;
		rk[x] += rk[y];
		ops.emplace_back(pii(x, y));
	}
}

void undo(int t)
{
	while((int)ops.size() > t)
	{
		auto [x, y] = ops.back();
		ops.pop_back();
		dsu[y] = y, rk[x] -= rk[y];
	}	
}

void init()
{
	for (int i = 1; i <= N; i++)
		dsu[i] = i, rk[i] = 1;
}


signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; i++)
		cin >> u[i] >> v[i] >> d[i];
	cin >> Q;
	for (int i = 1; i <= Q; i += B)
	{
		
		init();
		for (int j = 1; j <= M; j++)
			vis[j] = 0;
		// solve Q = [i, i + B - 1]
		vector<tuple<int, int, int>> change;
		vector<int> out;
		// d, i, 0: addedge
		// d, i, q: query i (ans[q])
		vector<tuple<int, int, int>> event;
		for (int j = i; j <= min(Q, i + B - 1); j++)
		{
			int t, a, b;
			cin >> t >> a >> b;
			if(t == 1)
			{	
				change.emplace_back(make_tuple(j, a, b));
				vis[a] = 1;
			}
			else 
				event.emplace_back(make_tuple(-b, j, a));
		}
		for (int j = 1; j <= M; j++)
			if(!vis[j])
				event.emplace_back(make_tuple(-d[j], 0, j));
			else
			{	
				change.emplace_back(make_tuple(i - 1, j, d[j]));
				out.emplace_back(j);
			}
		sort(event.begin(), event.end());
		sort(change.begin(), change.end());
		for (auto [d, q, j] : event)
		{
			//cerr << "event " << d << ' ' << t << ' ' << j << ' ' << q << '\n';

			if(q == 0)
			{
				//cerr << "include " << j << '\n';	
				merge(u[j], v[j]);
			}
			else
			{
				int T = ops.size();
				for (auto [tt, k, dd] : change)
					if(tt <= q)
						nd[k] = dd;
					else break;
				for (auto k : out)
					if(nd[k] >= -d)
					{
						//cerr << "tmp include " << k << '\n';	
						merge(u[k], v[k]);
					}
				ans[q] = rk[find(j)];
				undo(T);
			}
		}
		for (auto [t, j, dd] : change)
			d[j] = dd;
	
	}
	for (int i = 1; i <= Q; i++)
	{	
		if(ans[i] > 0)
			cout << ans[i] << '\n';
	}
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 508 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 11 ms 340 KB Output is correct
6 Correct 10 ms 340 KB Output is correct
7 Correct 12 ms 420 KB Output is correct
8 Correct 12 ms 424 KB Output is correct
9 Correct 15 ms 420 KB Output is correct
10 Correct 13 ms 460 KB Output is correct
11 Correct 14 ms 388 KB Output is correct
12 Correct 15 ms 432 KB Output is correct
13 Correct 15 ms 340 KB Output is correct
14 Correct 15 ms 340 KB Output is correct
15 Correct 13 ms 340 KB Output is correct
16 Correct 14 ms 392 KB Output is correct
17 Correct 13 ms 400 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1571 ms 135064 KB Output is correct
2 Correct 1498 ms 135008 KB Output is correct
3 Correct 1522 ms 135112 KB Output is correct
4 Correct 1463 ms 135064 KB Output is correct
5 Correct 1506 ms 135020 KB Output is correct
6 Correct 1737 ms 135016 KB Output is correct
7 Correct 1750 ms 135200 KB Output is correct
8 Correct 1773 ms 135212 KB Output is correct
9 Correct 33 ms 1228 KB Output is correct
10 Correct 1397 ms 135216 KB Output is correct
11 Correct 1517 ms 135228 KB Output is correct
12 Correct 1347 ms 135152 KB Output is correct
13 Correct 1422 ms 135128 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1094 ms 68648 KB Output is correct
2 Correct 490 ms 17888 KB Output is correct
3 Correct 1137 ms 68668 KB Output is correct
4 Correct 1154 ms 68668 KB Output is correct
5 Correct 43 ms 1132 KB Output is correct
6 Correct 1181 ms 68628 KB Output is correct
7 Correct 1097 ms 68608 KB Output is correct
8 Correct 1046 ms 68712 KB Output is correct
9 Correct 986 ms 68636 KB Output is correct
10 Correct 949 ms 68620 KB Output is correct
11 Correct 968 ms 68560 KB Output is correct
12 Correct 979 ms 68512 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2838 ms 137228 KB Output is correct
2 Correct 49 ms 1332 KB Output is correct
3 Correct 275 ms 5196 KB Output is correct
4 Correct 346 ms 5192 KB Output is correct
5 Correct 2831 ms 137088 KB Output is correct
6 Correct 2757 ms 137032 KB Output is correct
7 Correct 2884 ms 137072 KB Output is correct
8 Correct 1352 ms 135056 KB Output is correct
9 Correct 1376 ms 135012 KB Output is correct
10 Correct 1387 ms 134964 KB Output is correct
11 Correct 2040 ms 136348 KB Output is correct
12 Correct 2028 ms 136416 KB Output is correct
13 Correct 2119 ms 136352 KB Output is correct
14 Correct 2473 ms 137208 KB Output is correct
15 Correct 2424 ms 137120 KB Output is correct
16 Correct 2454 ms 137240 KB Output is correct
17 Correct 2427 ms 137120 KB Output is correct
18 Correct 2456 ms 137092 KB Output is correct
19 Correct 2428 ms 137296 KB Output is correct
20 Correct 2103 ms 136788 KB Output is correct
21 Correct 2079 ms 136612 KB Output is correct
22 Correct 2405 ms 136964 KB Output is correct
23 Correct 2185 ms 70896 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1571 ms 135064 KB Output is correct
2 Correct 1498 ms 135008 KB Output is correct
3 Correct 1522 ms 135112 KB Output is correct
4 Correct 1463 ms 135064 KB Output is correct
5 Correct 1506 ms 135020 KB Output is correct
6 Correct 1737 ms 135016 KB Output is correct
7 Correct 1750 ms 135200 KB Output is correct
8 Correct 1773 ms 135212 KB Output is correct
9 Correct 33 ms 1228 KB Output is correct
10 Correct 1397 ms 135216 KB Output is correct
11 Correct 1517 ms 135228 KB Output is correct
12 Correct 1347 ms 135152 KB Output is correct
13 Correct 1422 ms 135128 KB Output is correct
14 Correct 1094 ms 68648 KB Output is correct
15 Correct 490 ms 17888 KB Output is correct
16 Correct 1137 ms 68668 KB Output is correct
17 Correct 1154 ms 68668 KB Output is correct
18 Correct 43 ms 1132 KB Output is correct
19 Correct 1181 ms 68628 KB Output is correct
20 Correct 1097 ms 68608 KB Output is correct
21 Correct 1046 ms 68712 KB Output is correct
22 Correct 986 ms 68636 KB Output is correct
23 Correct 949 ms 68620 KB Output is correct
24 Correct 968 ms 68560 KB Output is correct
25 Correct 979 ms 68512 KB Output is correct
26 Correct 1497 ms 135276 KB Output is correct
27 Correct 1699 ms 135184 KB Output is correct
28 Correct 1599 ms 135272 KB Output is correct
29 Correct 1442 ms 135048 KB Output is correct
30 Correct 1683 ms 135180 KB Output is correct
31 Correct 1712 ms 135096 KB Output is correct
32 Correct 1696 ms 134976 KB Output is correct
33 Correct 1690 ms 135032 KB Output is correct
34 Correct 1690 ms 135144 KB Output is correct
35 Correct 1700 ms 135004 KB Output is correct
36 Correct 1616 ms 134968 KB Output is correct
37 Correct 1616 ms 135012 KB Output is correct
38 Correct 1578 ms 135024 KB Output is correct
39 Correct 1493 ms 135032 KB Output is correct
40 Correct 1484 ms 135000 KB Output is correct
41 Correct 1460 ms 135004 KB Output is correct
42 Correct 1346 ms 135116 KB Output is correct
43 Correct 1287 ms 135048 KB Output is correct
44 Correct 1315 ms 135080 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 508 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 11 ms 340 KB Output is correct
6 Correct 10 ms 340 KB Output is correct
7 Correct 12 ms 420 KB Output is correct
8 Correct 12 ms 424 KB Output is correct
9 Correct 15 ms 420 KB Output is correct
10 Correct 13 ms 460 KB Output is correct
11 Correct 14 ms 388 KB Output is correct
12 Correct 15 ms 432 KB Output is correct
13 Correct 15 ms 340 KB Output is correct
14 Correct 15 ms 340 KB Output is correct
15 Correct 13 ms 340 KB Output is correct
16 Correct 14 ms 392 KB Output is correct
17 Correct 13 ms 400 KB Output is correct
18 Correct 1571 ms 135064 KB Output is correct
19 Correct 1498 ms 135008 KB Output is correct
20 Correct 1522 ms 135112 KB Output is correct
21 Correct 1463 ms 135064 KB Output is correct
22 Correct 1506 ms 135020 KB Output is correct
23 Correct 1737 ms 135016 KB Output is correct
24 Correct 1750 ms 135200 KB Output is correct
25 Correct 1773 ms 135212 KB Output is correct
26 Correct 33 ms 1228 KB Output is correct
27 Correct 1397 ms 135216 KB Output is correct
28 Correct 1517 ms 135228 KB Output is correct
29 Correct 1347 ms 135152 KB Output is correct
30 Correct 1422 ms 135128 KB Output is correct
31 Correct 1094 ms 68648 KB Output is correct
32 Correct 490 ms 17888 KB Output is correct
33 Correct 1137 ms 68668 KB Output is correct
34 Correct 1154 ms 68668 KB Output is correct
35 Correct 43 ms 1132 KB Output is correct
36 Correct 1181 ms 68628 KB Output is correct
37 Correct 1097 ms 68608 KB Output is correct
38 Correct 1046 ms 68712 KB Output is correct
39 Correct 986 ms 68636 KB Output is correct
40 Correct 949 ms 68620 KB Output is correct
41 Correct 968 ms 68560 KB Output is correct
42 Correct 979 ms 68512 KB Output is correct
43 Correct 2838 ms 137228 KB Output is correct
44 Correct 49 ms 1332 KB Output is correct
45 Correct 275 ms 5196 KB Output is correct
46 Correct 346 ms 5192 KB Output is correct
47 Correct 2831 ms 137088 KB Output is correct
48 Correct 2757 ms 137032 KB Output is correct
49 Correct 2884 ms 137072 KB Output is correct
50 Correct 1352 ms 135056 KB Output is correct
51 Correct 1376 ms 135012 KB Output is correct
52 Correct 1387 ms 134964 KB Output is correct
53 Correct 2040 ms 136348 KB Output is correct
54 Correct 2028 ms 136416 KB Output is correct
55 Correct 2119 ms 136352 KB Output is correct
56 Correct 2473 ms 137208 KB Output is correct
57 Correct 2424 ms 137120 KB Output is correct
58 Correct 2454 ms 137240 KB Output is correct
59 Correct 2427 ms 137120 KB Output is correct
60 Correct 2456 ms 137092 KB Output is correct
61 Correct 2428 ms 137296 KB Output is correct
62 Correct 2103 ms 136788 KB Output is correct
63 Correct 2079 ms 136612 KB Output is correct
64 Correct 2405 ms 136964 KB Output is correct
65 Correct 2185 ms 70896 KB Output is correct
66 Correct 1497 ms 135276 KB Output is correct
67 Correct 1699 ms 135184 KB Output is correct
68 Correct 1599 ms 135272 KB Output is correct
69 Correct 1442 ms 135048 KB Output is correct
70 Correct 1683 ms 135180 KB Output is correct
71 Correct 1712 ms 135096 KB Output is correct
72 Correct 1696 ms 134976 KB Output is correct
73 Correct 1690 ms 135032 KB Output is correct
74 Correct 1690 ms 135144 KB Output is correct
75 Correct 1700 ms 135004 KB Output is correct
76 Correct 1616 ms 134968 KB Output is correct
77 Correct 1616 ms 135012 KB Output is correct
78 Correct 1578 ms 135024 KB Output is correct
79 Correct 1493 ms 135032 KB Output is correct
80 Correct 1484 ms 135000 KB Output is correct
81 Correct 1460 ms 135004 KB Output is correct
82 Correct 1346 ms 135116 KB Output is correct
83 Correct 1287 ms 135048 KB Output is correct
84 Correct 1315 ms 135080 KB Output is correct
85 Correct 2702 ms 137584 KB Output is correct
86 Correct 268 ms 5540 KB Output is correct
87 Correct 329 ms 5688 KB Output is correct
88 Correct 2721 ms 137716 KB Output is correct
89 Correct 2703 ms 137528 KB Output is correct
90 Correct 2769 ms 137484 KB Output is correct
91 Correct 1635 ms 135092 KB Output is correct
92 Correct 1623 ms 135164 KB Output is correct
93 Correct 1870 ms 135140 KB Output is correct
94 Correct 2180 ms 136816 KB Output is correct
95 Correct 2149 ms 136628 KB Output is correct
96 Correct 2186 ms 136508 KB Output is correct
97 Correct 2602 ms 137168 KB Output is correct
98 Correct 2704 ms 139160 KB Output is correct
99 Correct 2735 ms 140884 KB Output is correct
100 Correct 2682 ms 140968 KB Output is correct
101 Correct 2750 ms 140872 KB Output is correct
102 Correct 2769 ms 140872 KB Output is correct
103 Correct 2348 ms 139760 KB Output is correct
104 Correct 2443 ms 139588 KB Output is correct
105 Correct 2197 ms 139748 KB Output is correct
106 Correct 1917 ms 139584 KB Output is correct
107 Correct 2188 ms 139632 KB Output is correct
108 Correct 2589 ms 140368 KB Output is correct
109 Correct 2426 ms 72316 KB Output is correct