oj.uz

Submission #684221

# Submission time Handle Problem Language Result Execution time Memory
684221 2023-01-20T17:36:07 Z radal Bridges (APIO19_bridges) C++17
100 / 100
 2552 ms 11416 KB 
#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,avx2")
//#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
constexpr int N = 2e5+10,mod = 1e9+7,sq = 1500;
constexpr ll inf = 1e18+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}

vector<pll> e;
int W[N];
int par[N],sz[N],ans[N],lst[N];
bitset<N> mark;
vector<pair<int,pll> > Q;
vector<int> ve,pors,ch;
stack<int> st;

int getpar(int v){
	if (v == par[v]) return v;
	return getpar(par[v]);
}

bool cmp(int i,int j){
	return (W[i] > W[j]);
}

bool cmp2(int i,int j){
	return (Q[i].Y.Y > Q[j].Y.Y);
}

bool mg(int i){
	int u = e[i].X,v = e[i].Y;
	int p1 = getpar(u),p2 = getpar(v);
	if (p1 == p2) return 0;
	if (sz[p2] < sz[p1]) swap(p2,p1);
	par[p1] = p2;
	sz[p2] += sz[p1];
	st.push(p1);
	return 1;
}

void undo(){
	int u = st.top();
	st.pop();
	sz[par[u]] -= sz[u];
	par[u] = u;
}


int main(){
	ios :: sync_with_stdio(0); cin.tie(0);  cout.tie(0);
	int n,m;
	cin >> n >> m;
	rep(i,0,m){
		int u,v,w;
		cin >> u >> v >> w;
		e.pb({u,v});
		W[i] = w;
	}
	int q;
	cin >> q;
	rep(i,0,q){
		int t,u,v;
		cin >> t >> u >> v;
		if (t == 1) u--;
		Q.pb({t,{u,v}});
	}
	for (int l = 0; l < q; l += sq){
		int r = min(l+sq,q);
		pors.clear();
		ve.clear();
		ch.clear();
		mark.reset();
		rep(i,l,r){
			if (Q[i].X == 1) mark[Q[i].Y.X] = 1;
			else pors.pb(i);
		}
		rep(i,0,m){
		   	if (!mark[i]) ve.pb(i);
			else{
			   	ch.pb(i);
				lst[i] = W[i];
			}
		}
		sort(all(ve),cmp);
		sort(all(pors),cmp2);
		while (!st.empty()) st.pop();
		rep(i,1,n+1){
			par[i] = i;
			sz[i] = 1;
		}
		int p = 0;
		for (int i : pors){
			for (int j : ch) lst[j] = W[j];
			while (p < (int)ve.size() && W[ve[p]] >= Q[i].Y.Y){
				mg(ve[p]);
				p++;
			}
			int t = 0;
			rep(j,l,i){
				if (Q[j].X == 2) continue;
				lst[Q[j].Y.X] = Q[j].Y.Y;
			}
			for (int j : ch) if (lst[j] >= Q[i].Y.Y){
				t += mg(j);
			}
			ans[i] = sz[getpar(Q[i].Y.X)];
			while (t--) undo();
		}
		rep(i,l,r) if (Q[i].X == 1) W[Q[i].Y.X] = Q[i].Y.Y;
	}
	rep(i,0,q) if (Q[i].X == 2) cout << ans[i] << endl;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 44 ms 812 KB Output is correct
4 Correct 13 ms 792 KB Output is correct
5 Correct 20 ms 792 KB Output is correct
6 Correct 15 ms 792 KB Output is correct
7 Correct 17 ms 792 KB Output is correct
8 Correct 17 ms 792 KB Output is correct
9 Correct 19 ms 792 KB Output is correct
10 Correct 18 ms 792 KB Output is correct
11 Correct 18 ms 792 KB Output is correct
12 Correct 19 ms 792 KB Output is correct
13 Correct 26 ms 788 KB Output is correct
14 Correct 24 ms 788 KB Output is correct
15 Correct 20 ms 788 KB Output is correct
16 Correct 18 ms 792 KB Output is correct
17 Correct 19 ms 792 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1531 ms 5500 KB Output is correct
2 Correct 1541 ms 5616 KB Output is correct
3 Correct 1529 ms 5520 KB Output is correct
4 Correct 1492 ms 5528 KB Output is correct
5 Correct 1492 ms 5572 KB Output is correct
6 Correct 2279 ms 5816 KB Output is correct
7 Correct 2285 ms 5728 KB Output is correct
8 Correct 2303 ms 5816 KB Output is correct
9 Correct 102 ms 3500 KB Output is correct
10 Correct 1487 ms 5676 KB Output is correct
11 Correct 1396 ms 5620 KB Output is correct
12 Correct 1234 ms 5940 KB Output is correct
13 Correct 1109 ms 5408 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1327 ms 4616 KB Output is correct
2 Correct 1002 ms 3764 KB Output is correct
3 Correct 1555 ms 4772 KB Output is correct
4 Correct 1305 ms 4752 KB Output is correct
5 Correct 84 ms 3532 KB Output is correct
6 Correct 1477 ms 4696 KB Output is correct
7 Correct 1182 ms 4640 KB Output is correct
8 Correct 1022 ms 4648 KB Output is correct
9 Correct 801 ms 4748 KB Output is correct
10 Correct 698 ms 4736 KB Output is correct
11 Correct 747 ms 4636 KB Output is correct
12 Correct 638 ms 4532 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 7332 KB Output is correct
2 Correct 111 ms 3532 KB Output is correct
3 Correct 134 ms 3620 KB Output is correct
4 Correct 74 ms 3596 KB Output is correct
5 Correct 703 ms 7488 KB Output is correct
6 Correct 1210 ms 7680 KB Output is correct
7 Correct 664 ms 7652 KB Output is correct
8 Correct 583 ms 5464 KB Output is correct
9 Correct 598 ms 5400 KB Output is correct
10 Correct 595 ms 5692 KB Output is correct
11 Correct 911 ms 6800 KB Output is correct
12 Correct 884 ms 6680 KB Output is correct
13 Correct 929 ms 7016 KB Output is correct
14 Correct 614 ms 7504 KB Output is correct
15 Correct 629 ms 7532 KB Output is correct
16 Correct 1198 ms 7372 KB Output is correct
17 Correct 1203 ms 7360 KB Output is correct
18 Correct 1193 ms 7400 KB Output is correct
19 Correct 1162 ms 7380 KB Output is correct
20 Correct 1014 ms 7172 KB Output is correct
21 Correct 997 ms 7224 KB Output is correct
22 Correct 1151 ms 7468 KB Output is correct
23 Correct 707 ms 7172 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1531 ms 5500 KB Output is correct
2 Correct 1541 ms 5616 KB Output is correct
3 Correct 1529 ms 5520 KB Output is correct
4 Correct 1492 ms 5528 KB Output is correct
5 Correct 1492 ms 5572 KB Output is correct
6 Correct 2279 ms 5816 KB Output is correct
7 Correct 2285 ms 5728 KB Output is correct
8 Correct 2303 ms 5816 KB Output is correct
9 Correct 102 ms 3500 KB Output is correct
10 Correct 1487 ms 5676 KB Output is correct
11 Correct 1396 ms 5620 KB Output is correct
12 Correct 1234 ms 5940 KB Output is correct
13 Correct 1109 ms 5408 KB Output is correct
14 Correct 1327 ms 4616 KB Output is correct
15 Correct 1002 ms 3764 KB Output is correct
16 Correct 1555 ms 4772 KB Output is correct
17 Correct 1305 ms 4752 KB Output is correct
18 Correct 84 ms 3532 KB Output is correct
19 Correct 1477 ms 4696 KB Output is correct
20 Correct 1182 ms 4640 KB Output is correct
21 Correct 1022 ms 4648 KB Output is correct
22 Correct 801 ms 4748 KB Output is correct
23 Correct 698 ms 4736 KB Output is correct
24 Correct 747 ms 4636 KB Output is correct
25 Correct 638 ms 4532 KB Output is correct
26 Correct 1644 ms 5460 KB Output is correct
27 Correct 2102 ms 5580 KB Output is correct
28 Correct 1659 ms 5788 KB Output is correct
29 Correct 1073 ms 5632 KB Output is correct
30 Correct 1932 ms 5684 KB Output is correct
31 Correct 2005 ms 5556 KB Output is correct
32 Correct 2019 ms 5724 KB Output is correct
33 Correct 1625 ms 5648 KB Output is correct
34 Correct 1641 ms 5604 KB Output is correct
35 Correct 1637 ms 5476 KB Output is correct
36 Correct 1126 ms 5632 KB Output is correct
37 Correct 1115 ms 5560 KB Output is correct
38 Correct 1109 ms 5480 KB Output is correct
39 Correct 820 ms 5624 KB Output is correct
40 Correct 812 ms 5772 KB Output is correct
41 Correct 818 ms 5768 KB Output is correct
42 Correct 751 ms 5692 KB Output is correct
43 Correct 758 ms 5372 KB Output is correct
44 Correct 720 ms 5372 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 44 ms 812 KB Output is correct
4 Correct 13 ms 792 KB Output is correct
5 Correct 20 ms 792 KB Output is correct
6 Correct 15 ms 792 KB Output is correct
7 Correct 17 ms 792 KB Output is correct
8 Correct 17 ms 792 KB Output is correct
9 Correct 19 ms 792 KB Output is correct
10 Correct 18 ms 792 KB Output is correct
11 Correct 18 ms 792 KB Output is correct
12 Correct 19 ms 792 KB Output is correct
13 Correct 26 ms 788 KB Output is correct
14 Correct 24 ms 788 KB Output is correct
15 Correct 20 ms 788 KB Output is correct
16 Correct 18 ms 792 KB Output is correct
17 Correct 19 ms 792 KB Output is correct
18 Correct 1531 ms 5500 KB Output is correct
19 Correct 1541 ms 5616 KB Output is correct
20 Correct 1529 ms 5520 KB Output is correct
21 Correct 1492 ms 5528 KB Output is correct
22 Correct 1492 ms 5572 KB Output is correct
23 Correct 2279 ms 5816 KB Output is correct
24 Correct 2285 ms 5728 KB Output is correct
25 Correct 2303 ms 5816 KB Output is correct
26 Correct 102 ms 3500 KB Output is correct
27 Correct 1487 ms 5676 KB Output is correct
28 Correct 1396 ms 5620 KB Output is correct
29 Correct 1234 ms 5940 KB Output is correct
30 Correct 1109 ms 5408 KB Output is correct
31 Correct 1327 ms 4616 KB Output is correct
32 Correct 1002 ms 3764 KB Output is correct
33 Correct 1555 ms 4772 KB Output is correct
34 Correct 1305 ms 4752 KB Output is correct
35 Correct 84 ms 3532 KB Output is correct
36 Correct 1477 ms 4696 KB Output is correct
37 Correct 1182 ms 4640 KB Output is correct
38 Correct 1022 ms 4648 KB Output is correct
39 Correct 801 ms 4748 KB Output is correct
40 Correct 698 ms 4736 KB Output is correct
41 Correct 747 ms 4636 KB Output is correct
42 Correct 638 ms 4532 KB Output is correct
43 Correct 1182 ms 7332 KB Output is correct
44 Correct 111 ms 3532 KB Output is correct
45 Correct 134 ms 3620 KB Output is correct
46 Correct 74 ms 3596 KB Output is correct
47 Correct 703 ms 7488 KB Output is correct
48 Correct 1210 ms 7680 KB Output is correct
49 Correct 664 ms 7652 KB Output is correct
50 Correct 583 ms 5464 KB Output is correct
51 Correct 598 ms 5400 KB Output is correct
52 Correct 595 ms 5692 KB Output is correct
53 Correct 911 ms 6800 KB Output is correct
54 Correct 884 ms 6680 KB Output is correct
55 Correct 929 ms 7016 KB Output is correct
56 Correct 614 ms 7504 KB Output is correct
57 Correct 629 ms 7532 KB Output is correct
58 Correct 1198 ms 7372 KB Output is correct
59 Correct 1203 ms 7360 KB Output is correct
60 Correct 1193 ms 7400 KB Output is correct
61 Correct 1162 ms 7380 KB Output is correct
62 Correct 1014 ms 7172 KB Output is correct
63 Correct 997 ms 7224 KB Output is correct
64 Correct 1151 ms 7468 KB Output is correct
65 Correct 707 ms 7172 KB Output is correct
66 Correct 1644 ms 5460 KB Output is correct
67 Correct 2102 ms 5580 KB Output is correct
68 Correct 1659 ms 5788 KB Output is correct
69 Correct 1073 ms 5632 KB Output is correct
70 Correct 1932 ms 5684 KB Output is correct
71 Correct 2005 ms 5556 KB Output is correct
72 Correct 2019 ms 5724 KB Output is correct
73 Correct 1625 ms 5648 KB Output is correct
74 Correct 1641 ms 5604 KB Output is correct
75 Correct 1637 ms 5476 KB Output is correct
76 Correct 1126 ms 5632 KB Output is correct
77 Correct 1115 ms 5560 KB Output is correct
78 Correct 1109 ms 5480 KB Output is correct
79 Correct 820 ms 5624 KB Output is correct
80 Correct 812 ms 5772 KB Output is correct
81 Correct 818 ms 5768 KB Output is correct
82 Correct 751 ms 5692 KB Output is correct
83 Correct 758 ms 5372 KB Output is correct
84 Correct 720 ms 5372 KB Output is correct
85 Correct 1963 ms 7768 KB Output is correct
86 Correct 194 ms 4036 KB Output is correct
87 Correct 133 ms 3952 KB Output is correct
88 Correct 1401 ms 7840 KB Output is correct
89 Correct 1937 ms 7512 KB Output is correct
90 Correct 1399 ms 7576 KB Output is correct
91 Correct 1644 ms 5736 KB Output is correct
92 Correct 1625 ms 5748 KB Output is correct
93 Correct 2552 ms 5664 KB Output is correct
94 Correct 1701 ms 10304 KB Output is correct
95 Correct 1725 ms 10240 KB Output is correct
96 Correct 2045 ms 10244 KB Output is correct
97 Correct 869 ms 10020 KB Output is correct
98 Correct 935 ms 9528 KB Output is correct
99 Correct 1945 ms 11416 KB Output is correct
100 Correct 1917 ms 11252 KB Output is correct
101 Correct 1995 ms 11364 KB Output is correct
102 Correct 1982 ms 11372 KB Output is correct
103 Correct 2207 ms 10616 KB Output is correct
104 Correct 2220 ms 10592 KB Output is correct
105 Correct 1385 ms 10296 KB Output is correct
106 Correct 1078 ms 9856 KB Output is correct
107 Correct 1341 ms 10544 KB Output is correct
108 Correct 2004 ms 11140 KB Output is correct
109 Correct 1590 ms 9212 KB Output is correct