oj.uz

Submission #367491

# Submission time Handle Problem Language Result Execution time Memory
367491 2021-02-17T13:27:28 Z YJU Bridges (APIO19_bridges) C++14
100 / 100
 2967 ms 130676 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e5+5;
const ld pi=acos(-1);
//const ll INF=(1LL<<60);
const ll B=1000;
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

struct edge{
	ll x,y,c;
}ed[N];

vector<ll> query,changed,join[N],unchanged;
ll n,m,q,ty[N],id[N],w[N],ans[N];

bitset<N>vis;

ll dir[N],sz[N],stk[N],now;

inline ll f(ll idx){
	while(idx!=dir[idx])idx=dir[idx];
	return idx;
}

inline void uni(ll a,ll b){
	a=f(a);b=f(b);
	if(sz[a]>sz[b])swap(a,b);
	if(a==b){
		stk[++now]=0;
	}else{
		stk[++now]=a;
		dir[a]=b;
		sz[b]+=sz[a];
	}
}

inline void undo(){
	if(stk[now]==0){
		--now;
	}else{
		ll a=stk[now];
		sz[dir[a]]-=sz[a];
		dir[a]=a;
		--now;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,m)cin>>ed[i].x>>ed[i].y>>ed[i].c;
	cin>>q;
	REP1(i,q)cin>>ty[i]>>id[i]>>w[i];
	for(int i=1;i<=q;i+=B){
		//reset
		unchanged.clear();
		changed.clear();
		query.clear();
		REP1(j,n)dir[j]=j,sz[j]=1;
		//
		ll ql=i,qr=min(i+B,q+1)-1;
		for(int j=ql;j<=qr;++j){
			if(ty[j]==1){
				vis[id[j]]=1;
				changed.pb(id[j]);
			}else{
				query.pb(j);
			}
		}
		REP1(j,m)if(!vis[j])unchanged.pb(j);
		
		for(int j=ql;j<=qr;j++){
			if(ty[j]==1){
				ed[id[j]].c=w[j];
			}else{
				for(auto ii:changed){
					if(ed[ii].c>=w[j])join[j].pb(ii);
				}
			}
		}
		sort(unchanged.begin(),unchanged.end(),[&](ll a,ll b){
			return (ed[a].c>ed[b].c);
		});
		sort(query.begin(),query.end(),[&](ll a,ll b){
			return w[a]>w[b];
		});
		ll pos=0;
		for(auto j:query){
			while(pos<SZ(unchanged)&&ed[unchanged[pos]].c>=w[j])uni(ed[unchanged[pos]].x,ed[unchanged[pos]].y),++pos;
			ll ti=0;
			for(auto ii:join[j])++ti,uni(ed[ii].x,ed[ii].y);
			ans[j]=sz[f(id[j])];
			while(ti)undo(),ti--;
		}
		while(now>0)undo(),--now;
		
		for(int j:changed)vis[j]=0;
	}
	REP1(i,q)if(ty[i]==2)cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 44 ms 9580 KB Output is correct
4 Correct 6 ms 2924 KB Output is correct
5 Correct 45 ms 10476 KB Output is correct
6 Correct 35 ms 10476 KB Output is correct
7 Correct 41 ms 10604 KB Output is correct
8 Correct 47 ms 8940 KB Output is correct
9 Correct 55 ms 14828 KB Output is correct
10 Correct 50 ms 9708 KB Output is correct
11 Correct 47 ms 9580 KB Output is correct
12 Correct 57 ms 12012 KB Output is correct
13 Correct 55 ms 10220 KB Output is correct
14 Correct 50 ms 9324 KB Output is correct
15 Correct 56 ms 10092 KB Output is correct
16 Correct 50 ms 13036 KB Output is correct
17 Correct 50 ms 12140 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1666 ms 72960 KB Output is correct
2 Correct 1708 ms 72772 KB Output is correct
3 Correct 1693 ms 73072 KB Output is correct
4 Correct 1720 ms 72808 KB Output is correct
5 Correct 1719 ms 73328 KB Output is correct
6 Correct 2409 ms 130676 KB Output is correct
7 Correct 2425 ms 127328 KB Output is correct
8 Correct 2425 ms 127228 KB Output is correct
9 Correct 45 ms 4460 KB Output is correct
10 Correct 1365 ms 98736 KB Output is correct
11 Correct 1263 ms 98412 KB Output is correct
12 Correct 1537 ms 52868 KB Output is correct
13 Correct 1489 ms 45908 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1324 ms 72736 KB Output is correct
2 Correct 946 ms 97896 KB Output is correct
3 Correct 1604 ms 101000 KB Output is correct
4 Correct 1304 ms 72200 KB Output is correct
5 Correct 46 ms 4588 KB Output is correct
6 Correct 1473 ms 92012 KB Output is correct
7 Correct 1204 ms 64236 KB Output is correct
8 Correct 1064 ms 48492 KB Output is correct
9 Correct 919 ms 40276 KB Output is correct
10 Correct 841 ms 28792 KB Output is correct
11 Correct 926 ms 37868 KB Output is correct
12 Correct 822 ms 27756 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2136 ms 7276 KB Output is correct
2 Correct 45 ms 4460 KB Output is correct
3 Correct 221 ms 4972 KB Output is correct
4 Correct 113 ms 4972 KB Output is correct
5 Correct 1106 ms 7532 KB Output is correct
6 Correct 2117 ms 7532 KB Output is correct
7 Correct 1094 ms 7404 KB Output is correct
8 Correct 1047 ms 6128 KB Output is correct
9 Correct 1018 ms 6000 KB Output is correct
10 Correct 1014 ms 6320 KB Output is correct
11 Correct 1576 ms 6624 KB Output is correct
12 Correct 1574 ms 6592 KB Output is correct
13 Correct 1602 ms 6792 KB Output is correct
14 Correct 1012 ms 7404 KB Output is correct
15 Correct 1047 ms 7328 KB Output is correct
16 Correct 2155 ms 7388 KB Output is correct
17 Correct 2125 ms 7148 KB Output is correct
18 Correct 2198 ms 7148 KB Output is correct
19 Correct 2149 ms 7148 KB Output is correct
20 Correct 1782 ms 7188 KB Output is correct
21 Correct 1764 ms 7000 KB Output is correct
22 Correct 2045 ms 7276 KB Output is correct
23 Correct 1194 ms 7052 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1666 ms 72960 KB Output is correct
2 Correct 1708 ms 72772 KB Output is correct
3 Correct 1693 ms 73072 KB Output is correct
4 Correct 1720 ms 72808 KB Output is correct
5 Correct 1719 ms 73328 KB Output is correct
6 Correct 2409 ms 130676 KB Output is correct
7 Correct 2425 ms 127328 KB Output is correct
8 Correct 2425 ms 127228 KB Output is correct
9 Correct 45 ms 4460 KB Output is correct
10 Correct 1365 ms 98736 KB Output is correct
11 Correct 1263 ms 98412 KB Output is correct
12 Correct 1537 ms 52868 KB Output is correct
13 Correct 1489 ms 45908 KB Output is correct
14 Correct 1324 ms 72736 KB Output is correct
15 Correct 946 ms 97896 KB Output is correct
16 Correct 1604 ms 101000 KB Output is correct
17 Correct 1304 ms 72200 KB Output is correct
18 Correct 46 ms 4588 KB Output is correct
19 Correct 1473 ms 92012 KB Output is correct
20 Correct 1204 ms 64236 KB Output is correct
21 Correct 1064 ms 48492 KB Output is correct
22 Correct 919 ms 40276 KB Output is correct
23 Correct 841 ms 28792 KB Output is correct
24 Correct 926 ms 37868 KB Output is correct
25 Correct 822 ms 27756 KB Output is correct
26 Correct 1838 ms 72940 KB Output is correct
27 Correct 2080 ms 102200 KB Output is correct
28 Correct 1794 ms 71040 KB Output is correct
29 Correct 1318 ms 28244 KB Output is correct
30 Correct 2017 ms 88436 KB Output is correct
31 Correct 2027 ms 90952 KB Output is correct
32 Correct 2058 ms 91348 KB Output is correct
33 Correct 1757 ms 71660 KB Output is correct
34 Correct 1752 ms 71608 KB Output is correct
35 Correct 1792 ms 71896 KB Output is correct
36 Correct 1374 ms 35244 KB Output is correct
37 Correct 1351 ms 34056 KB Output is correct
38 Correct 1364 ms 32456 KB Output is correct
39 Correct 1158 ms 18372 KB Output is correct
40 Correct 1157 ms 17412 KB Output is correct
41 Correct 1145 ms 17040 KB Output is correct
42 Correct 1112 ms 16752 KB Output is correct
43 Correct 1105 ms 16384 KB Output is correct
44 Correct 1114 ms 15484 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 44 ms 9580 KB Output is correct
4 Correct 6 ms 2924 KB Output is correct
5 Correct 45 ms 10476 KB Output is correct
6 Correct 35 ms 10476 KB Output is correct
7 Correct 41 ms 10604 KB Output is correct
8 Correct 47 ms 8940 KB Output is correct
9 Correct 55 ms 14828 KB Output is correct
10 Correct 50 ms 9708 KB Output is correct
11 Correct 47 ms 9580 KB Output is correct
12 Correct 57 ms 12012 KB Output is correct
13 Correct 55 ms 10220 KB Output is correct
14 Correct 50 ms 9324 KB Output is correct
15 Correct 56 ms 10092 KB Output is correct
16 Correct 50 ms 13036 KB Output is correct
17 Correct 50 ms 12140 KB Output is correct
18 Correct 1666 ms 72960 KB Output is correct
19 Correct 1708 ms 72772 KB Output is correct
20 Correct 1693 ms 73072 KB Output is correct
21 Correct 1720 ms 72808 KB Output is correct
22 Correct 1719 ms 73328 KB Output is correct
23 Correct 2409 ms 130676 KB Output is correct
24 Correct 2425 ms 127328 KB Output is correct
25 Correct 2425 ms 127228 KB Output is correct
26 Correct 45 ms 4460 KB Output is correct
27 Correct 1365 ms 98736 KB Output is correct
28 Correct 1263 ms 98412 KB Output is correct
29 Correct 1537 ms 52868 KB Output is correct
30 Correct 1489 ms 45908 KB Output is correct
31 Correct 1324 ms 72736 KB Output is correct
32 Correct 946 ms 97896 KB Output is correct
33 Correct 1604 ms 101000 KB Output is correct
34 Correct 1304 ms 72200 KB Output is correct
35 Correct 46 ms 4588 KB Output is correct
36 Correct 1473 ms 92012 KB Output is correct
37 Correct 1204 ms 64236 KB Output is correct
38 Correct 1064 ms 48492 KB Output is correct
39 Correct 919 ms 40276 KB Output is correct
40 Correct 841 ms 28792 KB Output is correct
41 Correct 926 ms 37868 KB Output is correct
42 Correct 822 ms 27756 KB Output is correct
43 Correct 2136 ms 7276 KB Output is correct
44 Correct 45 ms 4460 KB Output is correct
45 Correct 221 ms 4972 KB Output is correct
46 Correct 113 ms 4972 KB Output is correct
47 Correct 1106 ms 7532 KB Output is correct
48 Correct 2117 ms 7532 KB Output is correct
49 Correct 1094 ms 7404 KB Output is correct
50 Correct 1047 ms 6128 KB Output is correct
51 Correct 1018 ms 6000 KB Output is correct
52 Correct 1014 ms 6320 KB Output is correct
53 Correct 1576 ms 6624 KB Output is correct
54 Correct 1574 ms 6592 KB Output is correct
55 Correct 1602 ms 6792 KB Output is correct
56 Correct 1012 ms 7404 KB Output is correct
57 Correct 1047 ms 7328 KB Output is correct
58 Correct 2155 ms 7388 KB Output is correct
59 Correct 2125 ms 7148 KB Output is correct
60 Correct 2198 ms 7148 KB Output is correct
61 Correct 2149 ms 7148 KB Output is correct
62 Correct 1782 ms 7188 KB Output is correct
63 Correct 1764 ms 7000 KB Output is correct
64 Correct 2045 ms 7276 KB Output is correct
65 Correct 1194 ms 7052 KB Output is correct
66 Correct 1838 ms 72940 KB Output is correct
67 Correct 2080 ms 102200 KB Output is correct
68 Correct 1794 ms 71040 KB Output is correct
69 Correct 1318 ms 28244 KB Output is correct
70 Correct 2017 ms 88436 KB Output is correct
71 Correct 2027 ms 90952 KB Output is correct
72 Correct 2058 ms 91348 KB Output is correct
73 Correct 1757 ms 71660 KB Output is correct
74 Correct 1752 ms 71608 KB Output is correct
75 Correct 1792 ms 71896 KB Output is correct
76 Correct 1374 ms 35244 KB Output is correct
77 Correct 1351 ms 34056 KB Output is correct
78 Correct 1364 ms 32456 KB Output is correct
79 Correct 1158 ms 18372 KB Output is correct
80 Correct 1157 ms 17412 KB Output is correct
81 Correct 1145 ms 17040 KB Output is correct
82 Correct 1112 ms 16752 KB Output is correct
83 Correct 1105 ms 16384 KB Output is correct
84 Correct 1114 ms 15484 KB Output is correct
85 Correct 2717 ms 74364 KB Output is correct
86 Correct 261 ms 11700 KB Output is correct
87 Correct 165 ms 15976 KB Output is correct
88 Correct 1645 ms 87620 KB Output is correct
89 Correct 2673 ms 72708 KB Output is correct
90 Correct 1676 ms 96236 KB Output is correct
91 Correct 1794 ms 73044 KB Output is correct
92 Correct 1785 ms 72792 KB Output is correct
93 Correct 2492 ms 110336 KB Output is correct
94 Correct 2247 ms 73832 KB Output is correct
95 Correct 2244 ms 73440 KB Output is correct
96 Correct 2622 ms 114288 KB Output is correct
97 Correct 1298 ms 40264 KB Output is correct
98 Correct 1316 ms 37008 KB Output is correct
99 Correct 2677 ms 75184 KB Output is correct
100 Correct 2683 ms 73792 KB Output is correct
101 Correct 2811 ms 73680 KB Output is correct
102 Correct 2840 ms 73704 KB Output is correct
103 Correct 2967 ms 119440 KB Output is correct
104 Correct 2955 ms 122176 KB Output is correct
105 Correct 2178 ms 50216 KB Output is correct
106 Correct 1775 ms 30056 KB Output is correct
107 Correct 2110 ms 56524 KB Output is correct
108 Correct 2746 ms 112872 KB Output is correct
109 Correct 1968 ms 116328 KB Output is correct