Submission #940832

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
940832	2024-03-07T17:36:35 Z	shadow_sami	Bridges (APIO19_bridges)	C++17	100 / 100	2806 ms	169188 KB

bridges

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
const ll blk = 450;

typedef struct Disjoint_Set_Union_Dynamic{
	vi par;
	vi sz;
	ll src,dest;
	vi lis;
	ll range;
	ll id;
	void init(ll k){
		range = k + 5;
		par.resize(range);
		sz.resize(range);
		fip(1,n+1){
			par[i] = i;
			sz[i] = 1;
		}
		return;
	}
	ll find(ll k){
		while(par[k]!=k)
			k = par[k];
		return k;
	}
	bool unite(ll u,ll v){
		src = find(u);
		dest = find(v);
		if(src==dest)
			return 0;
		if(sz[src]<sz[dest])
			swap(src,dest);
		par[dest] = src;
		sz[src] += sz[dest];
		lis.push_back(dest);
		return 1;
	}
	ll get(){
		return (ll)lis.size();
	}
	void rollback(ll k){
		while((ll)lis.size()>k){
			id = lis.back();
			sz[par[id]] -= sz[id];
			par[id] = id;
			lis.pop_back();
		}
		return;
	}
}DSU;

ll sr[mx];
ll de[mx];
ll we[mx];
ll pt[mx];
ll u[mx];
ll v[mx];
ll w[mx];
bool mark[mx];
ll na[mx];
vi lit[mx];
ll ptr = 0;

DSU dsu;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>m;
        fip(0,m)
        	cin>>sr[i]>>de[i]>>we[i];
        cin>>tp;
        fip(0,tp){
        	cin>>u[i]>>v[i]>>w[i];
        	if(u[i]==1)
        		v[i]--;
        }
        ll l,r;
        vi query,edge,vv;
        fip(0,tp){
        	l = i;
        	r = min(tp,i+blk);
        	query.clear();
        	edge.clear();
        	vv.clear();
        	fjp(0,m)
        		mark[j] = 0;
        	fjp(l,r){
        		if(u[j]==1){
        			mark[v[j]] = 1;
        		}
        	}
        	fjp(0,m){
        		if(!mark[j])
        			edge.push_back(j);
        		else
        			vv.push_back(j);
        	}
        	fjp(l,r){
        		if(u[j]==2){
        			query.push_back(j);
        			lit[j-l].clear();
        			fx(vv)
        				if(we[x]>=w[j])
        					lit[j-l].push_back(x);
        		}else{
        			we[v[j]] = w[j];
        		}
        	}
        	sort(query.begin(),query.end(),[](const ll aa,const ll bb){
        		return w[aa] > w[bb];
        	});
        	sort(edge.begin(),edge.end(),[](const ll aa,const ll bb){
        		return we[aa] > we[bb];
        	});
        	ptr = 0;
        	dsu.init(n);
        	fx(query){
        		while(ptr<(ll)edge.size() && we[edge[ptr]]>=w[x]){
        			tp2 = edge[ptr];
        			dsu.unite(sr[tp2],de[tp2]);
        			ptr++;
        		}
        		res = dsu.get();
        		for(auto y: lit[x-l])
        			dsu.unite(sr[y],de[y]);
        		na[x] = dsu.sz[dsu.find(v[x])];
        		dsu.rollback(res);        		
        	}
        	i += (blk-1);
        }
        fip(0,tp){
        	if(u[i]==1)
        		continue;
        	cout<<na[i]<<nli;
        }

    // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	25180 KB	Output is correct
2	Correct	5 ms	25180 KB	Output is correct
3	Correct	17 ms	26460 KB	Output is correct
4	Correct	8 ms	19292 KB	Output is correct
5	Correct	11 ms	25896 KB	Output is correct
6	Correct	12 ms	25692 KB	Output is correct
7	Correct	10 ms	25696 KB	Output is correct
8	Correct	11 ms	25692 KB	Output is correct
9	Correct	10 ms	25692 KB	Output is correct
10	Correct	11 ms	25916 KB	Output is correct
11	Correct	12 ms	25692 KB	Output is correct
12	Correct	12 ms	25944 KB	Output is correct
13	Correct	13 ms	25944 KB	Output is correct
14	Correct	13 ms	26204 KB	Output is correct
15	Correct	12 ms	25888 KB	Output is correct
16	Correct	10 ms	25688 KB	Output is correct
17	Correct	12 ms	25692 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1273 ms	164896 KB	Output is correct
2	Correct	1268 ms	166308 KB	Output is correct
3	Correct	1271 ms	165460 KB	Output is correct
4	Correct	1215 ms	164592 KB	Output is correct
5	Correct	1211 ms	164388 KB	Output is correct
6	Correct	1342 ms	164644 KB	Output is correct
7	Correct	1326 ms	165312 KB	Output is correct
8	Correct	1363 ms	164520 KB	Output is correct
9	Correct	29 ms	26452 KB	Output is correct
10	Correct	576 ms	165928 KB	Output is correct
11	Correct	608 ms	164004 KB	Output is correct
12	Correct	1217 ms	165156 KB	Output is correct
13	Correct	1199 ms	166236 KB	Output is correct

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	828 ms	99876 KB	Output is correct
2	Correct	286 ms	49612 KB	Output is correct
3	Correct	820 ms	98624 KB	Output is correct
4	Correct	805 ms	99352 KB	Output is correct
5	Correct	29 ms	26396 KB	Output is correct
6	Correct	826 ms	99368 KB	Output is correct
7	Correct	786 ms	98876 KB	Output is correct
8	Correct	762 ms	99632 KB	Output is correct
9	Correct	738 ms	98476 KB	Output is correct
10	Correct	729 ms	97660 KB	Output is correct
11	Correct	739 ms	100504 KB	Output is correct
12	Correct	724 ms	100140 KB	Output is correct

Subtask #4

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2659 ms	166072 KB	Output is correct
2	Correct	29 ms	26708 KB	Output is correct
3	Correct	259 ms	28124 KB	Output is correct
4	Correct	105 ms	28304 KB	Output is correct
5	Correct	1301 ms	165404 KB	Output is correct
6	Correct	2499 ms	167236 KB	Output is correct
7	Correct	1288 ms	166484 KB	Output is correct
8	Correct	1153 ms	165968 KB	Output is correct
9	Correct	1147 ms	164752 KB	Output is correct
10	Correct	1153 ms	165396 KB	Output is correct
11	Correct	1930 ms	167240 KB	Output is correct
12	Correct	1866 ms	167420 KB	Output is correct
13	Correct	1942 ms	166144 KB	Output is correct
14	Correct	1193 ms	165536 KB	Output is correct
15	Correct	1235 ms	165148 KB	Output is correct
16	Correct	2648 ms	167328 KB	Output is correct
17	Correct	2679 ms	168108 KB	Output is correct
18	Correct	2630 ms	166708 KB	Output is correct
19	Correct	2620 ms	168116 KB	Output is correct
20	Correct	2221 ms	166956 KB	Output is correct
21	Correct	2205 ms	166968 KB	Output is correct
22	Correct	2552 ms	167032 KB	Output is correct
23	Correct	1469 ms	165012 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1273 ms	164896 KB	Output is correct
2	Correct	1268 ms	166308 KB	Output is correct
3	Correct	1271 ms	165460 KB	Output is correct
4	Correct	1215 ms	164592 KB	Output is correct
5	Correct	1211 ms	164388 KB	Output is correct
6	Correct	1342 ms	164644 KB	Output is correct
7	Correct	1326 ms	165312 KB	Output is correct
8	Correct	1363 ms	164520 KB	Output is correct
9	Correct	29 ms	26452 KB	Output is correct
10	Correct	576 ms	165928 KB	Output is correct
11	Correct	608 ms	164004 KB	Output is correct
12	Correct	1217 ms	165156 KB	Output is correct
13	Correct	1199 ms	166236 KB	Output is correct
14	Correct	828 ms	99876 KB	Output is correct
15	Correct	286 ms	49612 KB	Output is correct
16	Correct	820 ms	98624 KB	Output is correct
17	Correct	805 ms	99352 KB	Output is correct
18	Correct	29 ms	26396 KB	Output is correct
19	Correct	826 ms	99368 KB	Output is correct
20	Correct	786 ms	98876 KB	Output is correct
21	Correct	762 ms	99632 KB	Output is correct
22	Correct	738 ms	98476 KB	Output is correct
23	Correct	729 ms	97660 KB	Output is correct
24	Correct	739 ms	100504 KB	Output is correct
25	Correct	724 ms	100140 KB	Output is correct
26	Correct	1234 ms	165212 KB	Output is correct
27	Correct	1337 ms	164456 KB	Output is correct
28	Correct	1305 ms	165876 KB	Output is correct
29	Correct	1225 ms	164376 KB	Output is correct
30	Correct	1317 ms	164492 KB	Output is correct
31	Correct	1323 ms	166692 KB	Output is correct
32	Correct	1332 ms	164420 KB	Output is correct
33	Correct	1293 ms	166164 KB	Output is correct
34	Correct	1281 ms	164912 KB	Output is correct
35	Correct	1308 ms	165948 KB	Output is correct
36	Correct	1216 ms	165392 KB	Output is correct
37	Correct	1232 ms	164340 KB	Output is correct
38	Correct	1216 ms	164644 KB	Output is correct
39	Correct	1179 ms	165164 KB	Output is correct
40	Correct	1188 ms	165288 KB	Output is correct
41	Correct	1200 ms	162280 KB	Output is correct
42	Correct	1121 ms	164076 KB	Output is correct
43	Correct	1149 ms	165672 KB	Output is correct
44	Correct	1183 ms	165224 KB	Output is correct

Subtask #6

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	25180 KB	Output is correct
2	Correct	5 ms	25180 KB	Output is correct
3	Correct	17 ms	26460 KB	Output is correct
4	Correct	8 ms	19292 KB	Output is correct
5	Correct	11 ms	25896 KB	Output is correct
6	Correct	12 ms	25692 KB	Output is correct
7	Correct	10 ms	25696 KB	Output is correct
8	Correct	11 ms	25692 KB	Output is correct
9	Correct	10 ms	25692 KB	Output is correct
10	Correct	11 ms	25916 KB	Output is correct
11	Correct	12 ms	25692 KB	Output is correct
12	Correct	12 ms	25944 KB	Output is correct
13	Correct	13 ms	25944 KB	Output is correct
14	Correct	13 ms	26204 KB	Output is correct
15	Correct	12 ms	25888 KB	Output is correct
16	Correct	10 ms	25688 KB	Output is correct
17	Correct	12 ms	25692 KB	Output is correct
18	Correct	1273 ms	164896 KB	Output is correct
19	Correct	1268 ms	166308 KB	Output is correct
20	Correct	1271 ms	165460 KB	Output is correct
21	Correct	1215 ms	164592 KB	Output is correct
22	Correct	1211 ms	164388 KB	Output is correct
23	Correct	1342 ms	164644 KB	Output is correct
24	Correct	1326 ms	165312 KB	Output is correct
25	Correct	1363 ms	164520 KB	Output is correct
26	Correct	29 ms	26452 KB	Output is correct
27	Correct	576 ms	165928 KB	Output is correct
28	Correct	608 ms	164004 KB	Output is correct
29	Correct	1217 ms	165156 KB	Output is correct
30	Correct	1199 ms	166236 KB	Output is correct
31	Correct	828 ms	99876 KB	Output is correct
32	Correct	286 ms	49612 KB	Output is correct
33	Correct	820 ms	98624 KB	Output is correct
34	Correct	805 ms	99352 KB	Output is correct
35	Correct	29 ms	26396 KB	Output is correct
36	Correct	826 ms	99368 KB	Output is correct
37	Correct	786 ms	98876 KB	Output is correct
38	Correct	762 ms	99632 KB	Output is correct
39	Correct	738 ms	98476 KB	Output is correct
40	Correct	729 ms	97660 KB	Output is correct
41	Correct	739 ms	100504 KB	Output is correct
42	Correct	724 ms	100140 KB	Output is correct
43	Correct	2659 ms	166072 KB	Output is correct
44	Correct	29 ms	26708 KB	Output is correct
45	Correct	259 ms	28124 KB	Output is correct
46	Correct	105 ms	28304 KB	Output is correct
47	Correct	1301 ms	165404 KB	Output is correct
48	Correct	2499 ms	167236 KB	Output is correct
49	Correct	1288 ms	166484 KB	Output is correct
50	Correct	1153 ms	165968 KB	Output is correct
51	Correct	1147 ms	164752 KB	Output is correct
52	Correct	1153 ms	165396 KB	Output is correct
53	Correct	1930 ms	167240 KB	Output is correct
54	Correct	1866 ms	167420 KB	Output is correct
55	Correct	1942 ms	166144 KB	Output is correct
56	Correct	1193 ms	165536 KB	Output is correct
57	Correct	1235 ms	165148 KB	Output is correct
58	Correct	2648 ms	167328 KB	Output is correct
59	Correct	2679 ms	168108 KB	Output is correct
60	Correct	2630 ms	166708 KB	Output is correct
61	Correct	2620 ms	168116 KB	Output is correct
62	Correct	2221 ms	166956 KB	Output is correct
63	Correct	2205 ms	166968 KB	Output is correct
64	Correct	2552 ms	167032 KB	Output is correct
65	Correct	1469 ms	165012 KB	Output is correct
66	Correct	1234 ms	165212 KB	Output is correct
67	Correct	1337 ms	164456 KB	Output is correct
68	Correct	1305 ms	165876 KB	Output is correct
69	Correct	1225 ms	164376 KB	Output is correct
70	Correct	1317 ms	164492 KB	Output is correct
71	Correct	1323 ms	166692 KB	Output is correct
72	Correct	1332 ms	164420 KB	Output is correct
73	Correct	1293 ms	166164 KB	Output is correct
74	Correct	1281 ms	164912 KB	Output is correct
75	Correct	1308 ms	165948 KB	Output is correct
76	Correct	1216 ms	165392 KB	Output is correct
77	Correct	1232 ms	164340 KB	Output is correct
78	Correct	1216 ms	164644 KB	Output is correct
79	Correct	1179 ms	165164 KB	Output is correct
80	Correct	1188 ms	165288 KB	Output is correct
81	Correct	1200 ms	162280 KB	Output is correct
82	Correct	1121 ms	164076 KB	Output is correct
83	Correct	1149 ms	165672 KB	Output is correct
84	Correct	1183 ms	165224 KB	Output is correct
85	Correct	2739 ms	168584 KB	Output is correct
86	Correct	272 ms	28960 KB	Output is correct
87	Correct	114 ms	29132 KB	Output is correct
88	Correct	1436 ms	166872 KB	Output is correct
89	Correct	2674 ms	168372 KB	Output is correct
90	Correct	1416 ms	166560 KB	Output is correct
91	Correct	1309 ms	166572 KB	Output is correct
92	Correct	1305 ms	166944 KB	Output is correct
93	Correct	1398 ms	167008 KB	Output is correct
94	Correct	2115 ms	168356 KB	Output is correct
95	Correct	2045 ms	167840 KB	Output is correct
96	Correct	2085 ms	166828 KB	Output is correct
97	Correct	1346 ms	167144 KB	Output is correct
98	Correct	1366 ms	168436 KB	Output is correct
99	Correct	2791 ms	167932 KB	Output is correct
100	Correct	2791 ms	168984 KB	Output is correct
101	Correct	2806 ms	168940 KB	Output is correct
102	Correct	2797 ms	169188 KB	Output is correct
103	Correct	2410 ms	167496 KB	Output is correct
104	Correct	2401 ms	168616 KB	Output is correct
105	Correct	2243 ms	167512 KB	Output is correct
106	Correct	1956 ms	167540 KB	Output is correct
107	Correct	2219 ms	166492 KB	Output is correct
108	Correct	2703 ms	169140 KB	Output is correct
109	Correct	1593 ms	167956 KB	Output is correct