oj.uz

Submission #209537

# Submission time Handle Problem Language Result Execution time Memory
209537 2020-03-14T12:48:42 Z mieszko11b Bridges (APIO19_bridges) C++14
100 / 100
 1979 ms 16756 KB 
#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

const int SQRT = 600;

int n, m;
int a[100007], b[100007], c[100007];
int q;
int t[100007], d[100007], e[100007], ans[100007];
bool changed[100007];
int lastw[100007];
int maxv;
vector<int> not_changed[200007];
vector<int> G[50007];

void readint(int &x) {
	x = 0;
	char c;
	do
		c = getchar_unlocked();
	while(c < '0' || c > '9');
	
	do {
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	} while(c >= '0' && c <= '9');
}

int p[50007], ran[50007];
bool vis[50007];

int cnt;
vector<int> aff;

void init_DSU() {
	for(int i = 1 ; i <= n ; i++) {
		p[i] = i;
		ran[i] = 1;
	}
}

int Find(int i) {
	if(p[i] == i)
		return i;
	return p[i] = Find(p[i]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	
	if(a == b)
		return ;
		
	if(ran[a] < ran[b]) {
		p[a] = b;
		ran[b] += ran[a];
	} else {
		p[b] = a;
		ran[a] += ran[b];
	}
}

void dfs(int w) {
	if(vis[w])
		return ;
	vis[w] = 1;
	aff.push_back(w);
	cnt += ran[w];
	for(int u : G[w])
		dfs(u);
}

int count(vector<ii> &E, int w) {
	for(ii e : E) {
		G[e.X].push_back(e.Y);
		G[e.Y].push_back(e.X);
	}
	cnt = 0;
	aff.reserve(100);
	dfs(Find(w));
	for(int x : aff)
		vis[x] = 0;
	aff.clear();
	for(ii e : E) {
		G[e.X].clear();
		G[e.Y].clear();
	}
	return cnt;
}


void process_queries(int x, int y) {
	vector<ii> Q;
	vector<int> chacha;
	chacha.reserve(y - x + 1);
	Q.reserve(y - x + 1);

	for(int i = x ; i <= y ; i++) {
		if(t[i] == 1)
			changed[d[i]] = 1;
		else
			Q.emplace_back(e[i], i);
	}
	for(int j = 0 ; j < maxv ; j++)
		not_changed[j].clear();
	for(int i = 1 ; i <= m ; i++) {
		if(!changed[i])
			not_changed[c[i]].push_back(i);
		else
			chacha.push_back(i);
	}
	sort(Q.begin(), Q.end(), greater<ii>());
	
	init_DSU();
	
	int v = maxv;
	for(int j = 0 ; j < Q.size() ; j++) {
		int q = Q[j].Y;
		
		for(int i = e[q] ; i < v ; i++)
			for(int e : not_changed[i])
				Union(a[e], b[e]);
		v = e[q];
				
		for(int e : chacha)
			lastw[e] = c[e];
		for(int k = x ; k < q ; k++)
			if(t[k] == 1)
				lastw[d[k]] = e[k];
		vector<ii> E;
		E.reserve(y - x + 1);
		for(int e : chacha)
			if(lastw[e] >= ::e[q])
				E.push_back({Find(a[e]), Find(b[e])});
		ans[q] = count(E, d[q]);
	}

	for(int k = x ; k <= y ; k++)
		if(t[k] == 1)
			c[d[k]] = e[k], changed[d[k]] = 0;
}

vector<int> hlp;
int renum(int x) {
	auto it = upper_bound(hlp.begin(), hlp.end(), x);
	return prev(it) - hlp.begin();
}	

int main() {
	//~ scanf("%d%d",&n, &m);
	readint(n);
	readint(m);
	
	for(int i = 1 ; i <= m ; i++) {
		//~ scanf("%d%d%d", &a[i], &b[i], &c[i]);
		readint(a[i]);
		readint(b[i]);
		readint(c[i]);
		//~ hlp.push_back(c[i]);
	}
	//~ scanf("%d", &q);
	readint(q);
	for(int i = 1 ; i <= q ; i++) {
		//~ scanf("%d%d%d", &t[i], &d[i], &e[i]);
		readint(t[i]);
		readint(d[i]);
		readint(e[i]);
		if(t[i] == 2)
			hlp.push_back(e[i]);
	}
	hlp.push_back(0);
	hlp.push_back(int(1e9) + 7);
		
	sort(hlp.begin(), hlp.end());
	hlp.resize(distance(hlp.begin(), unique(hlp.begin(), hlp.end())));
	maxv = hlp.size();
	for(int i = 1 ; i <= m ; i++)
		c[i] = renum(c[i]);
	//~ cout << endl;
	for(int i = 1 ; i <= q ; i++)
		e[i] = renum(e[i]);
	//~ cout << endl;
		
	for(int i = 1 ; i <= q ; i += SQRT)
		process_queries(i, min(i + SQRT - 1, q));
		
	for(int i = 1 ; i <= q ; i++)
		if(ans[i])
			printf("%d\n", ans[i]);
		
	return 0;
}

Compilation message

bridges.cpp: In function 'void process_queries(int, int)':
bridges.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < Q.size() ; j++) {
                  ~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6264 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 49 ms 6776 KB Output is correct
4 Correct 16 ms 6648 KB Output is correct
5 Correct 27 ms 6648 KB Output is correct
6 Correct 25 ms 6776 KB Output is correct
7 Correct 26 ms 6520 KB Output is correct
8 Correct 25 ms 6648 KB Output is correct
9 Correct 31 ms 6520 KB Output is correct
10 Correct 25 ms 6648 KB Output is correct
11 Correct 24 ms 6648 KB Output is correct
12 Correct 26 ms 6648 KB Output is correct
13 Correct 32 ms 6648 KB Output is correct
14 Correct 29 ms 6648 KB Output is correct
15 Correct 27 ms 6648 KB Output is correct
16 Correct 27 ms 6520 KB Output is correct
17 Correct 28 ms 6520 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1328 ms 12916 KB Output is correct
2 Correct 1258 ms 13684 KB Output is correct
3 Correct 1232 ms 13556 KB Output is correct
4 Correct 1223 ms 13556 KB Output is correct
5 Correct 1221 ms 13560 KB Output is correct
6 Correct 1101 ms 12532 KB Output is correct
7 Correct 1014 ms 12532 KB Output is correct
8 Correct 983 ms 12408 KB Output is correct
9 Correct 114 ms 9836 KB Output is correct
10 Correct 1012 ms 12404 KB Output is correct
11 Correct 938 ms 12532 KB Output is correct
12 Correct 571 ms 12144 KB Output is correct
13 Correct 493 ms 12500 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 12020 KB Output is correct
2 Correct 746 ms 10740 KB Output is correct
3 Correct 1080 ms 12404 KB Output is correct
4 Correct 999 ms 12592 KB Output is correct
5 Correct 114 ms 9840 KB Output is correct
6 Correct 992 ms 12532 KB Output is correct
7 Correct 883 ms 12532 KB Output is correct
8 Correct 810 ms 12404 KB Output is correct
9 Correct 703 ms 12144 KB Output is correct
10 Correct 677 ms 12144 KB Output is correct
11 Correct 543 ms 12028 KB Output is correct
12 Correct 501 ms 11896 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1578 ms 13016 KB Output is correct
2 Correct 114 ms 9840 KB Output is correct
3 Correct 104 ms 10104 KB Output is correct
4 Correct 52 ms 10012 KB Output is correct
5 Correct 635 ms 12656 KB Output is correct
6 Correct 1575 ms 13552 KB Output is correct
7 Correct 645 ms 12788 KB Output is correct
8 Correct 921 ms 12276 KB Output is correct
9 Correct 904 ms 12272 KB Output is correct
10 Correct 482 ms 11760 KB Output is correct
11 Correct 1371 ms 12912 KB Output is correct
12 Correct 1356 ms 13036 KB Output is correct
13 Correct 696 ms 12524 KB Output is correct
14 Correct 613 ms 12828 KB Output is correct
15 Correct 621 ms 12784 KB Output is correct
16 Correct 1709 ms 13552 KB Output is correct
17 Correct 1710 ms 13540 KB Output is correct
18 Correct 1686 ms 13552 KB Output is correct
19 Correct 1661 ms 13552 KB Output is correct
20 Correct 727 ms 12372 KB Output is correct
21 Correct 711 ms 12432 KB Output is correct
22 Correct 1031 ms 13068 KB Output is correct
23 Correct 593 ms 12336 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1328 ms 12916 KB Output is correct
2 Correct 1258 ms 13684 KB Output is correct
3 Correct 1232 ms 13556 KB Output is correct
4 Correct 1223 ms 13556 KB Output is correct
5 Correct 1221 ms 13560 KB Output is correct
6 Correct 1101 ms 12532 KB Output is correct
7 Correct 1014 ms 12532 KB Output is correct
8 Correct 983 ms 12408 KB Output is correct
9 Correct 114 ms 9836 KB Output is correct
10 Correct 1012 ms 12404 KB Output is correct
11 Correct 938 ms 12532 KB Output is correct
12 Correct 571 ms 12144 KB Output is correct
13 Correct 493 ms 12500 KB Output is correct
14 Correct 997 ms 12020 KB Output is correct
15 Correct 746 ms 10740 KB Output is correct
16 Correct 1080 ms 12404 KB Output is correct
17 Correct 999 ms 12592 KB Output is correct
18 Correct 114 ms 9840 KB Output is correct
19 Correct 992 ms 12532 KB Output is correct
20 Correct 883 ms 12532 KB Output is correct
21 Correct 810 ms 12404 KB Output is correct
22 Correct 703 ms 12144 KB Output is correct
23 Correct 677 ms 12144 KB Output is correct
24 Correct 543 ms 12028 KB Output is correct
25 Correct 501 ms 11896 KB Output is correct
26 Correct 1273 ms 13428 KB Output is correct
27 Correct 1439 ms 13300 KB Output is correct
28 Correct 1339 ms 13556 KB Output is correct
29 Correct 953 ms 13044 KB Output is correct
30 Correct 1559 ms 13428 KB Output is correct
31 Correct 1523 ms 13404 KB Output is correct
32 Correct 1509 ms 13300 KB Output is correct
33 Correct 1389 ms 13544 KB Output is correct
34 Correct 1389 ms 13524 KB Output is correct
35 Correct 1375 ms 13584 KB Output is correct
36 Correct 1069 ms 13272 KB Output is correct
37 Correct 1060 ms 13208 KB Output is correct
38 Correct 1016 ms 13172 KB Output is correct
39 Correct 944 ms 12784 KB Output is correct
40 Correct 928 ms 12784 KB Output is correct
41 Correct 949 ms 12692 KB Output is correct
42 Correct 682 ms 12792 KB Output is correct
43 Correct 667 ms 12792 KB Output is correct
44 Correct 668 ms 12792 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6264 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 49 ms 6776 KB Output is correct
4 Correct 16 ms 6648 KB Output is correct
5 Correct 27 ms 6648 KB Output is correct
6 Correct 25 ms 6776 KB Output is correct
7 Correct 26 ms 6520 KB Output is correct
8 Correct 25 ms 6648 KB Output is correct
9 Correct 31 ms 6520 KB Output is correct
10 Correct 25 ms 6648 KB Output is correct
11 Correct 24 ms 6648 KB Output is correct
12 Correct 26 ms 6648 KB Output is correct
13 Correct 32 ms 6648 KB Output is correct
14 Correct 29 ms 6648 KB Output is correct
15 Correct 27 ms 6648 KB Output is correct
16 Correct 27 ms 6520 KB Output is correct
17 Correct 28 ms 6520 KB Output is correct
18 Correct 1328 ms 12916 KB Output is correct
19 Correct 1258 ms 13684 KB Output is correct
20 Correct 1232 ms 13556 KB Output is correct
21 Correct 1223 ms 13556 KB Output is correct
22 Correct 1221 ms 13560 KB Output is correct
23 Correct 1101 ms 12532 KB Output is correct
24 Correct 1014 ms 12532 KB Output is correct
25 Correct 983 ms 12408 KB Output is correct
26 Correct 114 ms 9836 KB Output is correct
27 Correct 1012 ms 12404 KB Output is correct
28 Correct 938 ms 12532 KB Output is correct
29 Correct 571 ms 12144 KB Output is correct
30 Correct 493 ms 12500 KB Output is correct
31 Correct 997 ms 12020 KB Output is correct
32 Correct 746 ms 10740 KB Output is correct
33 Correct 1080 ms 12404 KB Output is correct
34 Correct 999 ms 12592 KB Output is correct
35 Correct 114 ms 9840 KB Output is correct
36 Correct 992 ms 12532 KB Output is correct
37 Correct 883 ms 12532 KB Output is correct
38 Correct 810 ms 12404 KB Output is correct
39 Correct 703 ms 12144 KB Output is correct
40 Correct 677 ms 12144 KB Output is correct
41 Correct 543 ms 12028 KB Output is correct
42 Correct 501 ms 11896 KB Output is correct
43 Correct 1578 ms 13016 KB Output is correct
44 Correct 114 ms 9840 KB Output is correct
45 Correct 104 ms 10104 KB Output is correct
46 Correct 52 ms 10012 KB Output is correct
47 Correct 635 ms 12656 KB Output is correct
48 Correct 1575 ms 13552 KB Output is correct
49 Correct 645 ms 12788 KB Output is correct
50 Correct 921 ms 12276 KB Output is correct
51 Correct 904 ms 12272 KB Output is correct
52 Correct 482 ms 11760 KB Output is correct
53 Correct 1371 ms 12912 KB Output is correct
54 Correct 1356 ms 13036 KB Output is correct
55 Correct 696 ms 12524 KB Output is correct
56 Correct 613 ms 12828 KB Output is correct
57 Correct 621 ms 12784 KB Output is correct
58 Correct 1709 ms 13552 KB Output is correct
59 Correct 1710 ms 13540 KB Output is correct
60 Correct 1686 ms 13552 KB Output is correct
61 Correct 1661 ms 13552 KB Output is correct
62 Correct 727 ms 12372 KB Output is correct
63 Correct 711 ms 12432 KB Output is correct
64 Correct 1031 ms 13068 KB Output is correct
65 Correct 593 ms 12336 KB Output is correct
66 Correct 1273 ms 13428 KB Output is correct
67 Correct 1439 ms 13300 KB Output is correct
68 Correct 1339 ms 13556 KB Output is correct
69 Correct 953 ms 13044 KB Output is correct
70 Correct 1559 ms 13428 KB Output is correct
71 Correct 1523 ms 13404 KB Output is correct
72 Correct 1509 ms 13300 KB Output is correct
73 Correct 1389 ms 13544 KB Output is correct
74 Correct 1389 ms 13524 KB Output is correct
75 Correct 1375 ms 13584 KB Output is correct
76 Correct 1069 ms 13272 KB Output is correct
77 Correct 1060 ms 13208 KB Output is correct
78 Correct 1016 ms 13172 KB Output is correct
79 Correct 944 ms 12784 KB Output is correct
80 Correct 928 ms 12784 KB Output is correct
81 Correct 949 ms 12692 KB Output is correct
82 Correct 682 ms 12792 KB Output is correct
83 Correct 667 ms 12792 KB Output is correct
84 Correct 668 ms 12792 KB Output is correct
85 Correct 1866 ms 14580 KB Output is correct
86 Correct 134 ms 10744 KB Output is correct
87 Correct 118 ms 10644 KB Output is correct
88 Correct 1167 ms 13940 KB Output is correct
89 Correct 1900 ms 16756 KB Output is correct
90 Correct 1144 ms 13556 KB Output is correct
91 Correct 1404 ms 14452 KB Output is correct
92 Correct 1337 ms 14708 KB Output is correct
93 Correct 1245 ms 12916 KB Output is correct
94 Correct 1720 ms 15860 KB Output is correct
95 Correct 1745 ms 15860 KB Output is correct
96 Correct 1272 ms 13680 KB Output is correct
97 Correct 825 ms 13424 KB Output is correct
98 Correct 802 ms 13516 KB Output is correct
99 Correct 1960 ms 16720 KB Output is correct
100 Correct 1960 ms 16756 KB Output is correct
101 Correct 1979 ms 16756 KB Output is correct
102 Correct 1978 ms 16644 KB Output is correct
103 Correct 1293 ms 13808 KB Output is correct
104 Correct 1291 ms 13808 KB Output is correct
105 Correct 850 ms 13604 KB Output is correct
106 Correct 681 ms 13424 KB Output is correct
107 Correct 958 ms 13988 KB Output is correct
108 Correct 1596 ms 15092 KB Output is correct
109 Correct 1232 ms 12528 KB Output is correct