oj.uz

Submission #739142

# Submission time Handle Problem Language Result Execution time Memory
739142 2023-05-10T03:42:35 Z josanneo22 Bridges (APIO19_bridges) C++17
100 / 100
 1935 ms 31800 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
 
const int B = 1000;
int n, m, q;
 
stack<int> stck;
int sz[100001], cmp[100001];
 
void reset() {
	iota(cmp + 1, cmp + 1 + n, 1);
	fill(sz + 1, sz + n + 1, 1);
}
 
inline int find(int a) {
	while (cmp[a] != a) a = cmp[a];
	return a;
}
 
void onion(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] > sz[b]) swap(a, b);
	stck.push(a);
	sz[b] += sz[a];
	cmp[a] = cmp[b];
}
 
void rollback(int x) {
	while (stck.size() > x) {
		int k = stck.top();
		stck.pop();
		sz[cmp[k]] -= sz[k];
		cmp[k] = k;
	}
}
 
int u[100001], v[100001], w[100001];
int t[100001], x[100001], y[100001];
bool changed[100001];
vector<int> to_join[B];
int ans[100001];
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd()
{
	int s=0;
	char ch=getchar(),last;
	while(ch<'0'||ch>'9') last=ch,ch=getchar();
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return last=='-'?-s:s;
}
int num[100];
inline void rt(int pp)
{
	if(pp<0) putchar('-'),pp=-pp;;
	int len=0;
	do num[len++]=pp%10;while(pp/=10);
	while(len--) putchar(num[len]+'0');
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    n=rd(); m=rd();
	FOR(i, 1, m + 1) {u[i]=rd();v[i]=rd();w[i]=rd();}
	q=rd();
	FOR(i, 1, q + 1) {t[i]=rd();x[i]=rd();y[i]=rd();}
 
	for (int l = 1; l <= q; l += B) {
		int r = min(q + 1, l + B);
		reset();
		fill(changed + 1, changed + m + 1, false);
 
		vector<int> ask, upd, unchanged;
		FOR(i, l, r) {
			if (t[i] == 1) {
				changed[x[i]] = true;
				upd.push_back(i);
			} else ask.push_back(i);
		}
		FOR(i, 1, m + 1) if (!changed[i]) unchanged.push_back(i);
 
		FOR(i, l, r) {
			if (t[i] == 1) w[x[i]] = y[i];
			else {
				to_join[i - l].clear();
				for (int j : upd)
					if (w[x[j]] >= y[i]) to_join[i - l].push_back(x[j]);
			}
		}
 
		sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });
		sort(unchanged.begin(), unchanged.end(),
		     [&](int a, int b) { return w[a] > w[b]; });
 
		int ptr = 0;
		for (int i : ask) {
			while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
				onion(u[unchanged[ptr]], v[unchanged[ptr]]);
				ptr++;
			}
			int prev_size = stck.size();
			for (int j : to_join[i - l]) onion(u[j], v[j]);
			ans[i] = sz[find(x[i])];
			rollback(prev_size);
		}
	}
 
	FOR(i, 1, q + 1) if (t[i] == 2){
        rt(ans[i]);
        printf("\n");
    }
	return 0;
}

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |  while (stck.size() > x) {
      |         ~~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:105:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
      |           ~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int rd()':
bridges.cpp:58:18: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  return last=='-'?-s:s;
      |         ~~~~~~~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 31 ms 3020 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 32 ms 3168 KB Output is correct
6 Correct 23 ms 2932 KB Output is correct
7 Correct 29 ms 3688 KB Output is correct
8 Correct 32 ms 2864 KB Output is correct
9 Correct 39 ms 4428 KB Output is correct
10 Correct 33 ms 3076 KB Output is correct
11 Correct 34 ms 2992 KB Output is correct
12 Correct 41 ms 3120 KB Output is correct
13 Correct 39 ms 2952 KB Output is correct
14 Correct 36 ms 2988 KB Output is correct
15 Correct 42 ms 2992 KB Output is correct
16 Correct 36 ms 4016 KB Output is correct
17 Correct 36 ms 3532 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 28584 KB Output is correct
2 Correct 1167 ms 28568 KB Output is correct
3 Correct 1154 ms 28712 KB Output is correct
4 Correct 1227 ms 28488 KB Output is correct
5 Correct 1212 ms 28788 KB Output is correct
6 Correct 1814 ms 30380 KB Output is correct
7 Correct 1835 ms 30436 KB Output is correct
8 Correct 1812 ms 30444 KB Output is correct
9 Correct 14 ms 3856 KB Output is correct
10 Correct 1004 ms 29984 KB Output is correct
11 Correct 931 ms 29888 KB Output is correct
12 Correct 1029 ms 27172 KB Output is correct
13 Correct 1037 ms 29832 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 977 ms 21056 KB Output is correct
2 Correct 758 ms 11652 KB Output is correct
3 Correct 1186 ms 23004 KB Output is correct
4 Correct 951 ms 21236 KB Output is correct
5 Correct 15 ms 3788 KB Output is correct
6 Correct 1099 ms 21232 KB Output is correct
7 Correct 886 ms 20904 KB Output is correct
8 Correct 789 ms 20732 KB Output is correct
9 Correct 670 ms 19488 KB Output is correct
10 Correct 596 ms 19548 KB Output is correct
11 Correct 661 ms 22536 KB Output is correct
12 Correct 567 ms 22480 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1367 ms 27548 KB Output is correct
2 Correct 15 ms 4044 KB Output is correct
3 Correct 135 ms 5416 KB Output is correct
4 Correct 50 ms 5308 KB Output is correct
5 Correct 675 ms 27636 KB Output is correct
6 Correct 1301 ms 27612 KB Output is correct
7 Correct 660 ms 27776 KB Output is correct
8 Correct 647 ms 26692 KB Output is correct
9 Correct 634 ms 26644 KB Output is correct
10 Correct 642 ms 26688 KB Output is correct
11 Correct 1010 ms 27356 KB Output is correct
12 Correct 977 ms 27396 KB Output is correct
13 Correct 1004 ms 27776 KB Output is correct
14 Correct 613 ms 27684 KB Output is correct
15 Correct 628 ms 27688 KB Output is correct
16 Correct 1330 ms 27996 KB Output is correct
17 Correct 1347 ms 27852 KB Output is correct
18 Correct 1351 ms 28064 KB Output is correct
19 Correct 1338 ms 27900 KB Output is correct
20 Correct 1118 ms 27872 KB Output is correct
21 Correct 1101 ms 27852 KB Output is correct
22 Correct 1293 ms 27544 KB Output is correct
23 Correct 790 ms 25708 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 28584 KB Output is correct
2 Correct 1167 ms 28568 KB Output is correct
3 Correct 1154 ms 28712 KB Output is correct
4 Correct 1227 ms 28488 KB Output is correct
5 Correct 1212 ms 28788 KB Output is correct
6 Correct 1814 ms 30380 KB Output is correct
7 Correct 1835 ms 30436 KB Output is correct
8 Correct 1812 ms 30444 KB Output is correct
9 Correct 14 ms 3856 KB Output is correct
10 Correct 1004 ms 29984 KB Output is correct
11 Correct 931 ms 29888 KB Output is correct
12 Correct 1029 ms 27172 KB Output is correct
13 Correct 1037 ms 29832 KB Output is correct
14 Correct 977 ms 21056 KB Output is correct
15 Correct 758 ms 11652 KB Output is correct
16 Correct 1186 ms 23004 KB Output is correct
17 Correct 951 ms 21236 KB Output is correct
18 Correct 15 ms 3788 KB Output is correct
19 Correct 1099 ms 21232 KB Output is correct
20 Correct 886 ms 20904 KB Output is correct
21 Correct 789 ms 20732 KB Output is correct
22 Correct 670 ms 19488 KB Output is correct
23 Correct 596 ms 19548 KB Output is correct
24 Correct 661 ms 22536 KB Output is correct
25 Correct 567 ms 22480 KB Output is correct
26 Correct 1283 ms 28936 KB Output is correct
27 Correct 1528 ms 30708 KB Output is correct
28 Correct 1242 ms 28980 KB Output is correct
29 Correct 864 ms 28432 KB Output is correct
30 Correct 1430 ms 30644 KB Output is correct
31 Correct 1469 ms 30948 KB Output is correct
32 Correct 1497 ms 30756 KB Output is correct
33 Correct 1236 ms 28856 KB Output is correct
34 Correct 1246 ms 28944 KB Output is correct
35 Correct 1257 ms 28828 KB Output is correct
36 Correct 928 ms 28612 KB Output is correct
37 Correct 918 ms 28364 KB Output is correct
38 Correct 900 ms 28588 KB Output is correct
39 Correct 741 ms 27028 KB Output is correct
40 Correct 746 ms 27344 KB Output is correct
41 Correct 740 ms 27176 KB Output is correct
42 Correct 740 ms 29044 KB Output is correct
43 Correct 738 ms 29020 KB Output is correct
44 Correct 726 ms 28912 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 31 ms 3020 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 32 ms 3168 KB Output is correct
6 Correct 23 ms 2932 KB Output is correct
7 Correct 29 ms 3688 KB Output is correct
8 Correct 32 ms 2864 KB Output is correct
9 Correct 39 ms 4428 KB Output is correct
10 Correct 33 ms 3076 KB Output is correct
11 Correct 34 ms 2992 KB Output is correct
12 Correct 41 ms 3120 KB Output is correct
13 Correct 39 ms 2952 KB Output is correct
14 Correct 36 ms 2988 KB Output is correct
15 Correct 42 ms 2992 KB Output is correct
16 Correct 36 ms 4016 KB Output is correct
17 Correct 36 ms 3532 KB Output is correct
18 Correct 1167 ms 28584 KB Output is correct
19 Correct 1167 ms 28568 KB Output is correct
20 Correct 1154 ms 28712 KB Output is correct
21 Correct 1227 ms 28488 KB Output is correct
22 Correct 1212 ms 28788 KB Output is correct
23 Correct 1814 ms 30380 KB Output is correct
24 Correct 1835 ms 30436 KB Output is correct
25 Correct 1812 ms 30444 KB Output is correct
26 Correct 14 ms 3856 KB Output is correct
27 Correct 1004 ms 29984 KB Output is correct
28 Correct 931 ms 29888 KB Output is correct
29 Correct 1029 ms 27172 KB Output is correct
30 Correct 1037 ms 29832 KB Output is correct
31 Correct 977 ms 21056 KB Output is correct
32 Correct 758 ms 11652 KB Output is correct
33 Correct 1186 ms 23004 KB Output is correct
34 Correct 951 ms 21236 KB Output is correct
35 Correct 15 ms 3788 KB Output is correct
36 Correct 1099 ms 21232 KB Output is correct
37 Correct 886 ms 20904 KB Output is correct
38 Correct 789 ms 20732 KB Output is correct
39 Correct 670 ms 19488 KB Output is correct
40 Correct 596 ms 19548 KB Output is correct
41 Correct 661 ms 22536 KB Output is correct
42 Correct 567 ms 22480 KB Output is correct
43 Correct 1367 ms 27548 KB Output is correct
44 Correct 15 ms 4044 KB Output is correct
45 Correct 135 ms 5416 KB Output is correct
46 Correct 50 ms 5308 KB Output is correct
47 Correct 675 ms 27636 KB Output is correct
48 Correct 1301 ms 27612 KB Output is correct
49 Correct 660 ms 27776 KB Output is correct
50 Correct 647 ms 26692 KB Output is correct
51 Correct 634 ms 26644 KB Output is correct
52 Correct 642 ms 26688 KB Output is correct
53 Correct 1010 ms 27356 KB Output is correct
54 Correct 977 ms 27396 KB Output is correct
55 Correct 1004 ms 27776 KB Output is correct
56 Correct 613 ms 27684 KB Output is correct
57 Correct 628 ms 27688 KB Output is correct
58 Correct 1330 ms 27996 KB Output is correct
59 Correct 1347 ms 27852 KB Output is correct
60 Correct 1351 ms 28064 KB Output is correct
61 Correct 1338 ms 27900 KB Output is correct
62 Correct 1118 ms 27872 KB Output is correct
63 Correct 1101 ms 27852 KB Output is correct
64 Correct 1293 ms 27544 KB Output is correct
65 Correct 790 ms 25708 KB Output is correct
66 Correct 1283 ms 28936 KB Output is correct
67 Correct 1528 ms 30708 KB Output is correct
68 Correct 1242 ms 28980 KB Output is correct
69 Correct 864 ms 28432 KB Output is correct
70 Correct 1430 ms 30644 KB Output is correct
71 Correct 1469 ms 30948 KB Output is correct
72 Correct 1497 ms 30756 KB Output is correct
73 Correct 1236 ms 28856 KB Output is correct
74 Correct 1246 ms 28944 KB Output is correct
75 Correct 1257 ms 28828 KB Output is correct
76 Correct 928 ms 28612 KB Output is correct
77 Correct 918 ms 28364 KB Output is correct
78 Correct 900 ms 28588 KB Output is correct
79 Correct 741 ms 27028 KB Output is correct
80 Correct 746 ms 27344 KB Output is correct
81 Correct 740 ms 27176 KB Output is correct
82 Correct 740 ms 29044 KB Output is correct
83 Correct 738 ms 29020 KB Output is correct
84 Correct 726 ms 28912 KB Output is correct
85 Correct 1767 ms 29900 KB Output is correct
86 Correct 153 ms 7284 KB Output is correct
87 Correct 89 ms 8684 KB Output is correct
88 Correct 1042 ms 31532 KB Output is correct
89 Correct 1783 ms 29992 KB Output is correct
90 Correct 1113 ms 31600 KB Output is correct
91 Correct 1260 ms 28808 KB Output is correct
92 Correct 1255 ms 28792 KB Output is correct
93 Correct 1876 ms 30444 KB Output is correct
94 Correct 1447 ms 30104 KB Output is correct
95 Correct 1466 ms 30076 KB Output is correct
96 Correct 1752 ms 31800 KB Output is correct
97 Correct 776 ms 28264 KB Output is correct
98 Correct 870 ms 31408 KB Output is correct
99 Correct 1757 ms 30396 KB Output is correct
100 Correct 1739 ms 30036 KB Output is correct
101 Correct 1819 ms 30180 KB Output is correct
102 Correct 1783 ms 30192 KB Output is correct
103 Correct 1935 ms 31768 KB Output is correct
104 Correct 1930 ms 31724 KB Output is correct
105 Correct 1426 ms 31344 KB Output is correct
106 Correct 1150 ms 31264 KB Output is correct
107 Correct 1329 ms 28360 KB Output is correct
108 Correct 1808 ms 30196 KB Output is correct
109 Correct 1286 ms 29556 KB Output is correct