oj.uz

Submission #251204

# Submission time Handle Problem Language Result Execution time Memory
251204 2020-07-20T15:09:44 Z _7_7_ Bridges (APIO19_bridges) C++14
100 / 100
 2338 ms 8072 KB 
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 

using namespace std;
using namespace __gnu_pbds;

//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 

 
 
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 1055;
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 1e5 + 11;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;

int timer;
struct DSU {
	int p[N], cnt[N];
	stack < int > st;

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

		while (sz(st))
			st.pop();
	}
	int get (int v) {
		return p[v] == v ? v : get(p[v]);
	}

	void merge (int v, int u) {
		v = get(v), u = get(u);
		if (v == u)
			return;
		if (cnt[v] < cnt[u])
			swap(v, u);
		st.push(u);
		p[u] = v;
		cnt[v] += cnt[u];
		++timer;
	}

	void undo () {
		int u = st.top();
		int v = p[u];
		st.pop();
		p[u] = u;
		cnt[v] -= cnt[u];
	}
} T;


vi nw;
vpii prv;
bool was[N];
vector < pair < pii, int > > a, b;
int n, m, q, v[N], u[N], w[N], tp, x, y, ww[N], res[N];


main () {
	fastio
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) 
		scanf("%d%d%d", &v[i], &u[i], &w[i]);

	scanf("%d", &q);
	for (int i = 1; i <= q; ++i) {
		scanf("%d%d%d", &tp, &x, &y);
		if (tp == 1) 
			a.pb({{x, y}, i});
		else
			b.pb({{y, x}, i});	
		
		if (i == q || i % block == 0) {
			T.init(n);
			for (int i = 1; i <= m; ++i) 
				was[i] = 0;
			
			sort(all(b));
			reverse(all(b));

			for (auto x : a)
				was[x.f.f] = 1;

			for (int i = 1; i <= m; ++i)
				if (!was[i])
					prv.pb({w[i], i});
				else
					nw.pb(i);

			sort(all(prv));
			reverse(all(prv));
			
			int j = 0;
			for (auto x : b) {
				while (j < sz(prv) && prv[j].f >= x.f.f)  {
					T.merge(v[prv[j].s], u[prv[j].s]); 
					++j;
				}

				for (auto y : nw)
					ww[y] = w[y];

				for (auto y : a)
					if (y.s <= x.s)
						ww[y.f.f] = y.f.s;
				
				timer = 0;	
				for (auto y : nw)
					if (ww[y] >= x.f.f)
						T.merge(v[y], u[y]);
								    
				res[x.s] = T.cnt[T.get(x.f.s)];
				while (timer--)
					T.undo();
			}
			for (auto y : a)
				w[y.f.f] = y.f.s;

			a.clear();
			b.clear();
			nw.clear();
			prv.clear();
		}
	}

	for (int i = 1; i <= q; ++i)
		if (res[i])
			printf("%d\n", res[i]);

	
}

Compilation message

bridges.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bridges.cpp: In function 'int main()':
bridges.cpp:94: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:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &v[i], &u[i], &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &tp, &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 34 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 17 ms 640 KB Output is correct
6 Correct 15 ms 640 KB Output is correct
7 Correct 19 ms 512 KB Output is correct
8 Correct 19 ms 640 KB Output is correct
9 Correct 20 ms 512 KB Output is correct
10 Correct 19 ms 640 KB Output is correct
11 Correct 22 ms 640 KB Output is correct
12 Correct 21 ms 640 KB Output is correct
13 Correct 24 ms 632 KB Output is correct
14 Correct 28 ms 640 KB Output is correct
15 Correct 20 ms 640 KB Output is correct
16 Correct 19 ms 512 KB Output is correct
17 Correct 19 ms 512 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1541 ms 2880 KB Output is correct
2 Correct 1498 ms 5496 KB Output is correct
3 Correct 1499 ms 5432 KB Output is correct
4 Correct 1475 ms 5904 KB Output is correct
5 Correct 1470 ms 5604 KB Output is correct
6 Correct 2080 ms 5496 KB Output is correct
7 Correct 2101 ms 5508 KB Output is correct
8 Correct 2091 ms 5508 KB Output is correct
9 Correct 50 ms 2352 KB Output is correct
10 Correct 1471 ms 4500 KB Output is correct
11 Correct 1442 ms 4392 KB Output is correct
12 Correct 1252 ms 5604 KB Output is correct
13 Correct 1154 ms 5460 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1208 ms 2220 KB Output is correct
2 Correct 879 ms 2836 KB Output is correct
3 Correct 1430 ms 4536 KB Output is correct
4 Correct 1205 ms 4612 KB Output is correct
5 Correct 58 ms 2296 KB Output is correct
6 Correct 1369 ms 4520 KB Output is correct
7 Correct 1121 ms 4416 KB Output is correct
8 Correct 998 ms 4748 KB Output is correct
9 Correct 765 ms 4712 KB Output is correct
10 Correct 689 ms 4480 KB Output is correct
11 Correct 761 ms 4608 KB Output is correct
12 Correct 688 ms 4356 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1498 ms 3976 KB Output is correct
2 Correct 49 ms 1020 KB Output is correct
3 Correct 173 ms 2800 KB Output is correct
4 Correct 139 ms 2800 KB Output is correct
5 Correct 1414 ms 3900 KB Output is correct
6 Correct 1442 ms 3884 KB Output is correct
7 Correct 1407 ms 3992 KB Output is correct
8 Correct 752 ms 2672 KB Output is correct
9 Correct 748 ms 2732 KB Output is correct
10 Correct 754 ms 2928 KB Output is correct
11 Correct 1188 ms 3396 KB Output is correct
12 Correct 1134 ms 3184 KB Output is correct
13 Correct 1142 ms 3436 KB Output is correct
14 Correct 1254 ms 4080 KB Output is correct
15 Correct 1357 ms 3912 KB Output is correct
16 Correct 1517 ms 4064 KB Output is correct
17 Correct 1524 ms 3844 KB Output is correct
18 Correct 1499 ms 4060 KB Output is correct
19 Correct 1477 ms 3952 KB Output is correct
20 Correct 1281 ms 3832 KB Output is correct
21 Correct 1321 ms 3896 KB Output is correct
22 Correct 1446 ms 3944 KB Output is correct
23 Correct 1342 ms 3640 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1541 ms 2880 KB Output is correct
2 Correct 1498 ms 5496 KB Output is correct
3 Correct 1499 ms 5432 KB Output is correct
4 Correct 1475 ms 5904 KB Output is correct
5 Correct 1470 ms 5604 KB Output is correct
6 Correct 2080 ms 5496 KB Output is correct
7 Correct 2101 ms 5508 KB Output is correct
8 Correct 2091 ms 5508 KB Output is correct
9 Correct 50 ms 2352 KB Output is correct
10 Correct 1471 ms 4500 KB Output is correct
11 Correct 1442 ms 4392 KB Output is correct
12 Correct 1252 ms 5604 KB Output is correct
13 Correct 1154 ms 5460 KB Output is correct
14 Correct 1208 ms 2220 KB Output is correct
15 Correct 879 ms 2836 KB Output is correct
16 Correct 1430 ms 4536 KB Output is correct
17 Correct 1205 ms 4612 KB Output is correct
18 Correct 58 ms 2296 KB Output is correct
19 Correct 1369 ms 4520 KB Output is correct
20 Correct 1121 ms 4416 KB Output is correct
21 Correct 998 ms 4748 KB Output is correct
22 Correct 765 ms 4712 KB Output is correct
23 Correct 689 ms 4480 KB Output is correct
24 Correct 761 ms 4608 KB Output is correct
25 Correct 688 ms 4356 KB Output is correct
26 Correct 1565 ms 5756 KB Output is correct
27 Correct 1917 ms 5376 KB Output is correct
28 Correct 1670 ms 5556 KB Output is correct
29 Correct 1182 ms 5876 KB Output is correct
30 Correct 1862 ms 5572 KB Output is correct
31 Correct 1868 ms 5496 KB Output is correct
32 Correct 1913 ms 5580 KB Output is correct
33 Correct 1623 ms 5712 KB Output is correct
34 Correct 1609 ms 5632 KB Output is correct
35 Correct 1612 ms 5636 KB Output is correct
36 Correct 1271 ms 5660 KB Output is correct
37 Correct 1262 ms 5456 KB Output is correct
38 Correct 1227 ms 5432 KB Output is correct
39 Correct 927 ms 5668 KB Output is correct
40 Correct 900 ms 5500 KB Output is correct
41 Correct 902 ms 5500 KB Output is correct
42 Correct 922 ms 5496 KB Output is correct
43 Correct 939 ms 5300 KB Output is correct
44 Correct 912 ms 5436 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 34 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 17 ms 640 KB Output is correct
6 Correct 15 ms 640 KB Output is correct
7 Correct 19 ms 512 KB Output is correct
8 Correct 19 ms 640 KB Output is correct
9 Correct 20 ms 512 KB Output is correct
10 Correct 19 ms 640 KB Output is correct
11 Correct 22 ms 640 KB Output is correct
12 Correct 21 ms 640 KB Output is correct
13 Correct 24 ms 632 KB Output is correct
14 Correct 28 ms 640 KB Output is correct
15 Correct 20 ms 640 KB Output is correct
16 Correct 19 ms 512 KB Output is correct
17 Correct 19 ms 512 KB Output is correct
18 Correct 1541 ms 2880 KB Output is correct
19 Correct 1498 ms 5496 KB Output is correct
20 Correct 1499 ms 5432 KB Output is correct
21 Correct 1475 ms 5904 KB Output is correct
22 Correct 1470 ms 5604 KB Output is correct
23 Correct 2080 ms 5496 KB Output is correct
24 Correct 2101 ms 5508 KB Output is correct
25 Correct 2091 ms 5508 KB Output is correct
26 Correct 50 ms 2352 KB Output is correct
27 Correct 1471 ms 4500 KB Output is correct
28 Correct 1442 ms 4392 KB Output is correct
29 Correct 1252 ms 5604 KB Output is correct
30 Correct 1154 ms 5460 KB Output is correct
31 Correct 1208 ms 2220 KB Output is correct
32 Correct 879 ms 2836 KB Output is correct
33 Correct 1430 ms 4536 KB Output is correct
34 Correct 1205 ms 4612 KB Output is correct
35 Correct 58 ms 2296 KB Output is correct
36 Correct 1369 ms 4520 KB Output is correct
37 Correct 1121 ms 4416 KB Output is correct
38 Correct 998 ms 4748 KB Output is correct
39 Correct 765 ms 4712 KB Output is correct
40 Correct 689 ms 4480 KB Output is correct
41 Correct 761 ms 4608 KB Output is correct
42 Correct 688 ms 4356 KB Output is correct
43 Correct 1498 ms 3976 KB Output is correct
44 Correct 49 ms 1020 KB Output is correct
45 Correct 173 ms 2800 KB Output is correct
46 Correct 139 ms 2800 KB Output is correct
47 Correct 1414 ms 3900 KB Output is correct
48 Correct 1442 ms 3884 KB Output is correct
49 Correct 1407 ms 3992 KB Output is correct
50 Correct 752 ms 2672 KB Output is correct
51 Correct 748 ms 2732 KB Output is correct
52 Correct 754 ms 2928 KB Output is correct
53 Correct 1188 ms 3396 KB Output is correct
54 Correct 1134 ms 3184 KB Output is correct
55 Correct 1142 ms 3436 KB Output is correct
56 Correct 1254 ms 4080 KB Output is correct
57 Correct 1357 ms 3912 KB Output is correct
58 Correct 1517 ms 4064 KB Output is correct
59 Correct 1524 ms 3844 KB Output is correct
60 Correct 1499 ms 4060 KB Output is correct
61 Correct 1477 ms 3952 KB Output is correct
62 Correct 1281 ms 3832 KB Output is correct
63 Correct 1321 ms 3896 KB Output is correct
64 Correct 1446 ms 3944 KB Output is correct
65 Correct 1342 ms 3640 KB Output is correct
66 Correct 1565 ms 5756 KB Output is correct
67 Correct 1917 ms 5376 KB Output is correct
68 Correct 1670 ms 5556 KB Output is correct
69 Correct 1182 ms 5876 KB Output is correct
70 Correct 1862 ms 5572 KB Output is correct
71 Correct 1868 ms 5496 KB Output is correct
72 Correct 1913 ms 5580 KB Output is correct
73 Correct 1623 ms 5712 KB Output is correct
74 Correct 1609 ms 5632 KB Output is correct
75 Correct 1612 ms 5636 KB Output is correct
76 Correct 1271 ms 5660 KB Output is correct
77 Correct 1262 ms 5456 KB Output is correct
78 Correct 1227 ms 5432 KB Output is correct
79 Correct 927 ms 5668 KB Output is correct
80 Correct 900 ms 5500 KB Output is correct
81 Correct 902 ms 5500 KB Output is correct
82 Correct 922 ms 5496 KB Output is correct
83 Correct 939 ms 5300 KB Output is correct
84 Correct 912 ms 5436 KB Output is correct
85 Correct 2134 ms 7948 KB Output is correct
86 Correct 211 ms 4856 KB Output is correct
87 Correct 176 ms 4972 KB Output is correct
88 Correct 1962 ms 6520 KB Output is correct
89 Correct 2083 ms 8056 KB Output is correct
90 Correct 2005 ms 6200 KB Output is correct
91 Correct 1672 ms 5372 KB Output is correct
92 Correct 1694 ms 5624 KB Output is correct
93 Correct 2338 ms 5464 KB Output is correct
94 Correct 1804 ms 6748 KB Output is correct
95 Correct 1862 ms 6652 KB Output is correct
96 Correct 1964 ms 6500 KB Output is correct
97 Correct 1606 ms 6412 KB Output is correct
98 Correct 1723 ms 6136 KB Output is correct
99 Correct 2170 ms 8072 KB Output is correct
100 Correct 2198 ms 7796 KB Output is correct
101 Correct 2234 ms 8028 KB Output is correct
102 Correct 2242 ms 7804 KB Output is correct
103 Correct 2274 ms 6904 KB Output is correct
104 Correct 2163 ms 6928 KB Output is correct
105 Correct 1630 ms 6772 KB Output is correct
106 Correct 1334 ms 6392 KB Output is correct
107 Correct 1493 ms 7412 KB Output is correct
108 Correct 2073 ms 7640 KB Output is correct
109 Correct 1934 ms 5736 KB Output is correct