oj.uz

Submission #130479

# Submission time Handle Problem Language Result Execution time Memory
130479 2019-07-15T09:54:04 Z ZwariowanyMarcin Bridges (APIO19_bridges) C++14
100 / 100
 2566 ms 13700 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, n) for(int i = 1; i <= n; ++i) 
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;



using namespace std;
using namespace __gnu_pbds;

// order_by_key
// find_by_order
// tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Plus, Minus;

const int nax = 1e5 + 5, blok = 700;

struct eve {
	int l, r, nr, w;
	bool operator < (eve b) const {
		return w < b.w;
	}
};

struct qu {
	int x, s, w;
	bool operator < (qu b) const {
		return w < b.w;
	}
};

int n, m, a, b, c, q;
int last[nax], tim[nax];
pair <int, int> e[nax];

vector <eve> v;
vector <qu> Q;

int ans[nax];

struct dsu {
	int p[nax];
	int siz[nax];
	void init() {
		for(int i = 1; i <= n; ++i) {
			p[i] = i;
			siz[i] = 1;
		}
	}
	int Find(int x) {
		if(x == p[x])
			return x;
		return p[x] = Find(p[x]);
	}
	void Onion(int x, int y) {
		x = Find(x);
		y = Find(y);
		if(x != y) {
			if(siz[x] > siz[y])
				swap(x, y);
			p[x] = y;
			siz[y] += siz[x];
		}
	}
};

int cnt = 1;
int odw[nax];

vector <int> g[nax];
vector <int> del;

dsu D;

void add(eve X) {
	int id = X.nr;
	g[D.Find(e[id].fi)].pb(D.Find(e[id].se));
	g[D.Find(e[id].se)].pb(D.Find(e[id].fi));
	del.pb(D.Find(e[id].fi));
	del.pb(D.Find(e[id].se));
}

int res = 0;

void dfs(int u) {
	odw[u] = cnt;
	res += D.siz[u];
	for(auto it: g[u]) {
		if(odw[it] != cnt)
			dfs(it);
	}
}
	

void go(int L, int R) {
	for(int i = 1; i <= n; ++i)
		odw[i] = 0;
	cnt = 0;
	D.init();
	vector <qu> daj;
	for(auto it: Q) {
		if(L <= it.x && it.x <= R) {
			daj.pb(it);
		}
	}
	sort(daj.begin(), daj.end());
	vector <eve> mid;
	int point = ss(v) - 1;
	while(ss(daj)) {
		auto it = daj.back();
		daj.pop_back();
		while(point >= 0 && v[point].w >= it.w) {
			if(v[point].l > R || v[point].r < L) {
				;
			}
			else if(v[point].l <= L && v[point].r >= R) {
				D.Onion(e[v[point].nr].fi, e[v[point].nr].se);
			}
			else
				mid.pb(v[point]);
			point--;
		}
		cnt++;
		for(auto kan: mid) {
			if(kan.l <= it.x && it.x <= kan.r) {
				add(kan);
			}
		}
		
		res = 0;
		dfs(D.Find(it.s));
		ans[it.x] = res;
		
		for(auto it: del) {
			g[it].clear();
		}
		del.clear();
	}
}		
		


int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &a, &b, &c);
		e[i] = mp(a, b);
		last[i] = c;
	}
	
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i) {
		int type;
		scanf("%d%d%d", &type, &a, &b);
		if(type == 1) {
			v.pb({tim[a], i - 1, a, last[a]});
			tim[a] = i;
			last[a] = b;
		}
		else {
			Q.pb({i, a, b});
		}
	}
	for(int i = 1; i <= m; ++i) {
		v.pb({tim[i], q, i, last[i]});
	}
	
	for(int i = 1; i <= q; ++i)
		ans[i] = -1;
		
	sort(v.begin(), v.end());
	
	for(int i = 1; i <= q; i += blok) {
		go(i, min(i + blok - 1, q));
	}
	
	for(int i = 1; i <= q; ++i) {
		if(ans[i] != -1)
			printf("%d\n", ans[i]);
	}
	
	

	return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &type, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2748 KB Output is correct
3 Correct 56 ms 3244 KB Output is correct
4 Correct 10 ms 3128 KB Output is correct
5 Correct 29 ms 3192 KB Output is correct
6 Correct 24 ms 3192 KB Output is correct
7 Correct 28 ms 3064 KB Output is correct
8 Correct 28 ms 3192 KB Output is correct
9 Correct 38 ms 3196 KB Output is correct
10 Correct 26 ms 3192 KB Output is correct
11 Correct 26 ms 3192 KB Output is correct
12 Correct 31 ms 3192 KB Output is correct
13 Correct 35 ms 3192 KB Output is correct
14 Correct 31 ms 3192 KB Output is correct
15 Correct 30 ms 3192 KB Output is correct
16 Correct 30 ms 3192 KB Output is correct
17 Correct 29 ms 3064 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1491 ms 11056 KB Output is correct
2 Correct 1507 ms 11104 KB Output is correct
3 Correct 1470 ms 11008 KB Output is correct
4 Correct 1424 ms 11080 KB Output is correct
5 Correct 1415 ms 11000 KB Output is correct
6 Correct 2566 ms 9904 KB Output is correct
7 Correct 2374 ms 9860 KB Output is correct
8 Correct 2322 ms 9868 KB Output is correct
9 Correct 73 ms 5868 KB Output is correct
10 Correct 1768 ms 9640 KB Output is correct
11 Correct 1603 ms 9840 KB Output is correct
12 Correct 1006 ms 10388 KB Output is correct
13 Correct 1396 ms 10596 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1261 ms 9524 KB Output is correct
2 Correct 1143 ms 7072 KB Output is correct
3 Correct 1597 ms 9360 KB Output is correct
4 Correct 1231 ms 9500 KB Output is correct
5 Correct 73 ms 5992 KB Output is correct
6 Correct 1385 ms 9372 KB Output is correct
7 Correct 1120 ms 9520 KB Output is correct
8 Correct 903 ms 9432 KB Output is correct
9 Correct 636 ms 9324 KB Output is correct
10 Correct 562 ms 9328 KB Output is correct
11 Correct 968 ms 9580 KB Output is correct
12 Correct 762 ms 9516 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 12936 KB Output is correct
2 Correct 74 ms 5864 KB Output is correct
3 Correct 102 ms 7980 KB Output is correct
4 Correct 64 ms 8108 KB Output is correct
5 Correct 685 ms 11412 KB Output is correct
6 Correct 885 ms 13000 KB Output is correct
7 Correct 693 ms 11328 KB Output is correct
8 Correct 608 ms 10064 KB Output is correct
9 Correct 600 ms 10244 KB Output is correct
10 Correct 608 ms 10068 KB Output is correct
11 Correct 870 ms 11360 KB Output is correct
12 Correct 869 ms 11624 KB Output is correct
13 Correct 838 ms 11548 KB Output is correct
14 Correct 635 ms 11488 KB Output is correct
15 Correct 672 ms 11368 KB Output is correct
16 Correct 976 ms 12760 KB Output is correct
17 Correct 989 ms 12768 KB Output is correct
18 Correct 993 ms 12868 KB Output is correct
19 Correct 1002 ms 12884 KB Output is correct
20 Correct 931 ms 11848 KB Output is correct
21 Correct 945 ms 11832 KB Output is correct
22 Correct 944 ms 12596 KB Output is correct
23 Correct 799 ms 10648 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1491 ms 11056 KB Output is correct
2 Correct 1507 ms 11104 KB Output is correct
3 Correct 1470 ms 11008 KB Output is correct
4 Correct 1424 ms 11080 KB Output is correct
5 Correct 1415 ms 11000 KB Output is correct
6 Correct 2566 ms 9904 KB Output is correct
7 Correct 2374 ms 9860 KB Output is correct
8 Correct 2322 ms 9868 KB Output is correct
9 Correct 73 ms 5868 KB Output is correct
10 Correct 1768 ms 9640 KB Output is correct
11 Correct 1603 ms 9840 KB Output is correct
12 Correct 1006 ms 10388 KB Output is correct
13 Correct 1396 ms 10596 KB Output is correct
14 Correct 1261 ms 9524 KB Output is correct
15 Correct 1143 ms 7072 KB Output is correct
16 Correct 1597 ms 9360 KB Output is correct
17 Correct 1231 ms 9500 KB Output is correct
18 Correct 73 ms 5992 KB Output is correct
19 Correct 1385 ms 9372 KB Output is correct
20 Correct 1120 ms 9520 KB Output is correct
21 Correct 903 ms 9432 KB Output is correct
22 Correct 636 ms 9324 KB Output is correct
23 Correct 562 ms 9328 KB Output is correct
24 Correct 968 ms 9580 KB Output is correct
25 Correct 762 ms 9516 KB Output is correct
26 Correct 1601 ms 10992 KB Output is correct
27 Correct 2001 ms 10736 KB Output is correct
28 Correct 1559 ms 11052 KB Output is correct
29 Correct 1056 ms 10884 KB Output is correct
30 Correct 2071 ms 10752 KB Output is correct
31 Correct 2056 ms 11004 KB Output is correct
32 Correct 2101 ms 10852 KB Output is correct
33 Correct 1641 ms 10924 KB Output is correct
34 Correct 1659 ms 10916 KB Output is correct
35 Correct 1647 ms 10956 KB Output is correct
36 Correct 1179 ms 10708 KB Output is correct
37 Correct 1128 ms 11008 KB Output is correct
38 Correct 1146 ms 11040 KB Output is correct
39 Correct 774 ms 10356 KB Output is correct
40 Correct 746 ms 10476 KB Output is correct
41 Correct 745 ms 10396 KB Output is correct
42 Correct 965 ms 11152 KB Output is correct
43 Correct 996 ms 11260 KB Output is correct
44 Correct 935 ms 11192 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2748 KB Output is correct
3 Correct 56 ms 3244 KB Output is correct
4 Correct 10 ms 3128 KB Output is correct
5 Correct 29 ms 3192 KB Output is correct
6 Correct 24 ms 3192 KB Output is correct
7 Correct 28 ms 3064 KB Output is correct
8 Correct 28 ms 3192 KB Output is correct
9 Correct 38 ms 3196 KB Output is correct
10 Correct 26 ms 3192 KB Output is correct
11 Correct 26 ms 3192 KB Output is correct
12 Correct 31 ms 3192 KB Output is correct
13 Correct 35 ms 3192 KB Output is correct
14 Correct 31 ms 3192 KB Output is correct
15 Correct 30 ms 3192 KB Output is correct
16 Correct 30 ms 3192 KB Output is correct
17 Correct 29 ms 3064 KB Output is correct
18 Correct 1491 ms 11056 KB Output is correct
19 Correct 1507 ms 11104 KB Output is correct
20 Correct 1470 ms 11008 KB Output is correct
21 Correct 1424 ms 11080 KB Output is correct
22 Correct 1415 ms 11000 KB Output is correct
23 Correct 2566 ms 9904 KB Output is correct
24 Correct 2374 ms 9860 KB Output is correct
25 Correct 2322 ms 9868 KB Output is correct
26 Correct 73 ms 5868 KB Output is correct
27 Correct 1768 ms 9640 KB Output is correct
28 Correct 1603 ms 9840 KB Output is correct
29 Correct 1006 ms 10388 KB Output is correct
30 Correct 1396 ms 10596 KB Output is correct
31 Correct 1261 ms 9524 KB Output is correct
32 Correct 1143 ms 7072 KB Output is correct
33 Correct 1597 ms 9360 KB Output is correct
34 Correct 1231 ms 9500 KB Output is correct
35 Correct 73 ms 5992 KB Output is correct
36 Correct 1385 ms 9372 KB Output is correct
37 Correct 1120 ms 9520 KB Output is correct
38 Correct 903 ms 9432 KB Output is correct
39 Correct 636 ms 9324 KB Output is correct
40 Correct 562 ms 9328 KB Output is correct
41 Correct 968 ms 9580 KB Output is correct
42 Correct 762 ms 9516 KB Output is correct
43 Correct 886 ms 12936 KB Output is correct
44 Correct 74 ms 5864 KB Output is correct
45 Correct 102 ms 7980 KB Output is correct
46 Correct 64 ms 8108 KB Output is correct
47 Correct 685 ms 11412 KB Output is correct
48 Correct 885 ms 13000 KB Output is correct
49 Correct 693 ms 11328 KB Output is correct
50 Correct 608 ms 10064 KB Output is correct
51 Correct 600 ms 10244 KB Output is correct
52 Correct 608 ms 10068 KB Output is correct
53 Correct 870 ms 11360 KB Output is correct
54 Correct 869 ms 11624 KB Output is correct
55 Correct 838 ms 11548 KB Output is correct
56 Correct 635 ms 11488 KB Output is correct
57 Correct 672 ms 11368 KB Output is correct
58 Correct 976 ms 12760 KB Output is correct
59 Correct 989 ms 12768 KB Output is correct
60 Correct 993 ms 12868 KB Output is correct
61 Correct 1002 ms 12884 KB Output is correct
62 Correct 931 ms 11848 KB Output is correct
63 Correct 945 ms 11832 KB Output is correct
64 Correct 944 ms 12596 KB Output is correct
65 Correct 799 ms 10648 KB Output is correct
66 Correct 1601 ms 10992 KB Output is correct
67 Correct 2001 ms 10736 KB Output is correct
68 Correct 1559 ms 11052 KB Output is correct
69 Correct 1056 ms 10884 KB Output is correct
70 Correct 2071 ms 10752 KB Output is correct
71 Correct 2056 ms 11004 KB Output is correct
72 Correct 2101 ms 10852 KB Output is correct
73 Correct 1641 ms 10924 KB Output is correct
74 Correct 1659 ms 10916 KB Output is correct
75 Correct 1647 ms 10956 KB Output is correct
76 Correct 1179 ms 10708 KB Output is correct
77 Correct 1128 ms 11008 KB Output is correct
78 Correct 1146 ms 11040 KB Output is correct
79 Correct 774 ms 10356 KB Output is correct
80 Correct 746 ms 10476 KB Output is correct
81 Correct 745 ms 10396 KB Output is correct
82 Correct 965 ms 11152 KB Output is correct
83 Correct 996 ms 11260 KB Output is correct
84 Correct 935 ms 11192 KB Output is correct
85 Correct 1823 ms 13376 KB Output is correct
86 Correct 160 ms 8432 KB Output is correct
87 Correct 163 ms 8404 KB Output is correct
88 Correct 1675 ms 11656 KB Output is correct
89 Correct 1861 ms 13700 KB Output is correct
90 Correct 1685 ms 11280 KB Output is correct
91 Correct 1676 ms 10940 KB Output is correct
92 Correct 1611 ms 11096 KB Output is correct
93 Correct 2410 ms 10152 KB Output is correct
94 Correct 1781 ms 12464 KB Output is correct
95 Correct 1819 ms 12340 KB Output is correct
96 Correct 2261 ms 11384 KB Output is correct
97 Correct 980 ms 11628 KB Output is correct
98 Correct 1241 ms 11580 KB Output is correct
99 Correct 1867 ms 13472 KB Output is correct
100 Correct 1884 ms 13428 KB Output is correct
101 Correct 1901 ms 13416 KB Output is correct
102 Correct 1929 ms 13280 KB Output is correct
103 Correct 2406 ms 12132 KB Output is correct
104 Correct 2368 ms 12132 KB Output is correct
105 Correct 1661 ms 11908 KB Output is correct
106 Correct 1381 ms 11700 KB Output is correct
107 Correct 1343 ms 12140 KB Output is correct
108 Correct 2220 ms 12420 KB Output is correct
109 Correct 2109 ms 10176 KB Output is correct