oj.uz

Submission #361376

# Submission time Handle Problem Language Result Execution time Memory
361376 2021-01-29T15:44:48 Z AmineWeslati Bridges (APIO19_bridges) C++14
100 / 100
 2500 ms 133384 KB 
//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////

const int  B=1000;

int N,M,Q;
int v[MX],u[MX],w[MX];
int t[MX],x[MX],y[MX];
vi join[MX];

int szz[MX],p[MX];
vi stk;

void reset(){
	FOR(i,1,N+1) szz[i]=1,p[i]=i;
	stk.clear();
}

int findSet(int u){
	while(p[u]!=u) u=p[u];
	return u;
}

void onion(int u, int v){
	u=findSet(u),v=findSet(v);
	if(u==v) return;
	if(szz[u]<szz[v]) swap(u,v);
	p[v]=u;
	szz[u]+=szz[v];
	stk.pb(v);
}

void rollback(int x){
	while(sz(stk)>x){
		int u=stk.back(); 
		stk.pop_back();
		szz[p[u]]-=szz[u];
		p[u]=u;
	}
}


int main() {
    boost; IO();

    cin>>N>>M;
    FOR(i,1,M+1){
    	cin>>u[i]>>v[i]>>w[i];
    }
    cin>>Q;
    FOR(i,1,Q+1){
    	cin>>t[i]>>x[i]>>y[i];
    }

    int ans[Q+1];
    for(int idx=1; idx<=Q; idx+=B){
    	int l=idx,r=min(Q,idx+B-1);

    	V<bool>vis(M+1,0);
    	vi changed,unchanged,ask;
    	FOR(j,l,r+1){
    		if(t[j]==1){
    			vis[x[j]]=1;
    			changed.pb(x[j]);
    		}
    		else{
    			ask.pb(j);
    		}
    	} 
    	FOR(i,1,M+1) if(!vis[i]) unchanged.pb(i);

    	FOR(j,l,r+1){
    		if(t[j]==1){
    			w[x[j]]=y[j];
    		}
    		else{
    			for(auto k: changed) if(w[k]>=y[j]) join[j].pb(k);
    		}
    	} 

    	sort(all(unchanged), [&](int i, int j){return w[i]>w[j];});
    	sort(all(ask), [&](int i, int j){return y[i]>y[j];});


    	reset();

    	int ptr=-1;
    	for(int q: ask){
    		while(ptr+1<sz(unchanged) && w[unchanged[ptr+1]]>=y[q]){
    			ptr++;
    			onion(u[unchanged[ptr]],v[unchanged[ptr]]);
    		}	

    		int init=sz(stk);
    		for(auto ed: join[q]) onion(u[ed],v[ed]);
    		ans[q]=szz[findSet(x[q])];
    		rollback(init);
    	}
    }

    FOR(i,1,Q+1) if(t[i]==2) cout << ans[i] << endl;
    

    return 0;
}
//Change your approach

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 44 ms 11884 KB Output is correct
4 Correct 7 ms 5228 KB Output is correct
5 Correct 45 ms 12652 KB Output is correct
6 Correct 35 ms 12908 KB Output is correct
7 Correct 40 ms 12908 KB Output is correct
8 Correct 44 ms 11244 KB Output is correct
9 Correct 57 ms 17260 KB Output is correct
10 Correct 46 ms 12140 KB Output is correct
11 Correct 47 ms 11884 KB Output is correct
12 Correct 56 ms 14444 KB Output is correct
13 Correct 54 ms 12524 KB Output is correct
14 Correct 49 ms 11884 KB Output is correct
15 Correct 54 ms 12524 KB Output is correct
16 Correct 50 ms 15468 KB Output is correct
17 Correct 49 ms 14572 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1465 ms 75176 KB Output is correct
2 Correct 1474 ms 75180 KB Output is correct
3 Correct 1468 ms 75460 KB Output is correct
4 Correct 1510 ms 75052 KB Output is correct
5 Correct 1519 ms 75688 KB Output is correct
6 Correct 2213 ms 133384 KB Output is correct
7 Correct 2204 ms 129960 KB Output is correct
8 Correct 2265 ms 129660 KB Output is correct
9 Correct 47 ms 6892 KB Output is correct
10 Correct 1264 ms 101400 KB Output is correct
11 Correct 1170 ms 100652 KB Output is correct
12 Correct 1286 ms 55344 KB Output is correct
13 Correct 1270 ms 48432 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1138 ms 75244 KB Output is correct
2 Correct 896 ms 100128 KB Output is correct
3 Correct 1364 ms 103232 KB Output is correct
4 Correct 1123 ms 74772 KB Output is correct
5 Correct 45 ms 6892 KB Output is correct
6 Correct 1284 ms 94596 KB Output is correct
7 Correct 1040 ms 66728 KB Output is correct
8 Correct 904 ms 50796 KB Output is correct
9 Correct 776 ms 42860 KB Output is correct
10 Correct 687 ms 31084 KB Output is correct
11 Correct 779 ms 40300 KB Output is correct
12 Correct 667 ms 30172 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1636 ms 9808 KB Output is correct
2 Correct 45 ms 8172 KB Output is correct
3 Correct 175 ms 9244 KB Output is correct
4 Correct 87 ms 9372 KB Output is correct
5 Correct 811 ms 12132 KB Output is correct
6 Correct 1605 ms 13920 KB Output is correct
7 Correct 809 ms 12260 KB Output is correct
8 Correct 803 ms 11288 KB Output is correct
9 Correct 793 ms 11160 KB Output is correct
10 Correct 797 ms 10988 KB Output is correct
11 Correct 1211 ms 12580 KB Output is correct
12 Correct 1192 ms 12612 KB Output is correct
13 Correct 1223 ms 12612 KB Output is correct
14 Correct 737 ms 12176 KB Output is correct
15 Correct 779 ms 12260 KB Output is correct
16 Correct 1633 ms 13928 KB Output is correct
17 Correct 1652 ms 13544 KB Output is correct
18 Correct 1654 ms 13668 KB Output is correct
19 Correct 1641 ms 13672 KB Output is correct
20 Correct 1368 ms 12836 KB Output is correct
21 Correct 1367 ms 12752 KB Output is correct
22 Correct 1565 ms 13688 KB Output is correct
23 Correct 919 ms 11688 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1465 ms 75176 KB Output is correct
2 Correct 1474 ms 75180 KB Output is correct
3 Correct 1468 ms 75460 KB Output is correct
4 Correct 1510 ms 75052 KB Output is correct
5 Correct 1519 ms 75688 KB Output is correct
6 Correct 2213 ms 133384 KB Output is correct
7 Correct 2204 ms 129960 KB Output is correct
8 Correct 2265 ms 129660 KB Output is correct
9 Correct 47 ms 6892 KB Output is correct
10 Correct 1264 ms 101400 KB Output is correct
11 Correct 1170 ms 100652 KB Output is correct
12 Correct 1286 ms 55344 KB Output is correct
13 Correct 1270 ms 48432 KB Output is correct
14 Correct 1138 ms 75244 KB Output is correct
15 Correct 896 ms 100128 KB Output is correct
16 Correct 1364 ms 103232 KB Output is correct
17 Correct 1123 ms 74772 KB Output is correct
18 Correct 45 ms 6892 KB Output is correct
19 Correct 1284 ms 94596 KB Output is correct
20 Correct 1040 ms 66728 KB Output is correct
21 Correct 904 ms 50796 KB Output is correct
22 Correct 776 ms 42860 KB Output is correct
23 Correct 687 ms 31084 KB Output is correct
24 Correct 779 ms 40300 KB Output is correct
25 Correct 667 ms 30172 KB Output is correct
26 Correct 1445 ms 75296 KB Output is correct
27 Correct 1866 ms 104872 KB Output is correct
28 Correct 1543 ms 73368 KB Output is correct
29 Correct 1070 ms 30768 KB Output is correct
30 Correct 1787 ms 90792 KB Output is correct
31 Correct 1810 ms 93488 KB Output is correct
32 Correct 1846 ms 93832 KB Output is correct
33 Correct 1531 ms 73904 KB Output is correct
34 Correct 1529 ms 73812 KB Output is correct
35 Correct 1534 ms 74264 KB Output is correct
36 Correct 1153 ms 37544 KB Output is correct
37 Correct 1125 ms 36524 KB Output is correct
38 Correct 1113 ms 34688 KB Output is correct
39 Correct 934 ms 20860 KB Output is correct
40 Correct 931 ms 19904 KB Output is correct
41 Correct 928 ms 19640 KB Output is correct
42 Correct 896 ms 19160 KB Output is correct
43 Correct 910 ms 18948 KB Output is correct
44 Correct 889 ms 17928 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 44 ms 11884 KB Output is correct
4 Correct 7 ms 5228 KB Output is correct
5 Correct 45 ms 12652 KB Output is correct
6 Correct 35 ms 12908 KB Output is correct
7 Correct 40 ms 12908 KB Output is correct
8 Correct 44 ms 11244 KB Output is correct
9 Correct 57 ms 17260 KB Output is correct
10 Correct 46 ms 12140 KB Output is correct
11 Correct 47 ms 11884 KB Output is correct
12 Correct 56 ms 14444 KB Output is correct
13 Correct 54 ms 12524 KB Output is correct
14 Correct 49 ms 11884 KB Output is correct
15 Correct 54 ms 12524 KB Output is correct
16 Correct 50 ms 15468 KB Output is correct
17 Correct 49 ms 14572 KB Output is correct
18 Correct 1465 ms 75176 KB Output is correct
19 Correct 1474 ms 75180 KB Output is correct
20 Correct 1468 ms 75460 KB Output is correct
21 Correct 1510 ms 75052 KB Output is correct
22 Correct 1519 ms 75688 KB Output is correct
23 Correct 2213 ms 133384 KB Output is correct
24 Correct 2204 ms 129960 KB Output is correct
25 Correct 2265 ms 129660 KB Output is correct
26 Correct 47 ms 6892 KB Output is correct
27 Correct 1264 ms 101400 KB Output is correct
28 Correct 1170 ms 100652 KB Output is correct
29 Correct 1286 ms 55344 KB Output is correct
30 Correct 1270 ms 48432 KB Output is correct
31 Correct 1138 ms 75244 KB Output is correct
32 Correct 896 ms 100128 KB Output is correct
33 Correct 1364 ms 103232 KB Output is correct
34 Correct 1123 ms 74772 KB Output is correct
35 Correct 45 ms 6892 KB Output is correct
36 Correct 1284 ms 94596 KB Output is correct
37 Correct 1040 ms 66728 KB Output is correct
38 Correct 904 ms 50796 KB Output is correct
39 Correct 776 ms 42860 KB Output is correct
40 Correct 687 ms 31084 KB Output is correct
41 Correct 779 ms 40300 KB Output is correct
42 Correct 667 ms 30172 KB Output is correct
43 Correct 1636 ms 9808 KB Output is correct
44 Correct 45 ms 8172 KB Output is correct
45 Correct 175 ms 9244 KB Output is correct
46 Correct 87 ms 9372 KB Output is correct
47 Correct 811 ms 12132 KB Output is correct
48 Correct 1605 ms 13920 KB Output is correct
49 Correct 809 ms 12260 KB Output is correct
50 Correct 803 ms 11288 KB Output is correct
51 Correct 793 ms 11160 KB Output is correct
52 Correct 797 ms 10988 KB Output is correct
53 Correct 1211 ms 12580 KB Output is correct
54 Correct 1192 ms 12612 KB Output is correct
55 Correct 1223 ms 12612 KB Output is correct
56 Correct 737 ms 12176 KB Output is correct
57 Correct 779 ms 12260 KB Output is correct
58 Correct 1633 ms 13928 KB Output is correct
59 Correct 1652 ms 13544 KB Output is correct
60 Correct 1654 ms 13668 KB Output is correct
61 Correct 1641 ms 13672 KB Output is correct
62 Correct 1368 ms 12836 KB Output is correct
63 Correct 1367 ms 12752 KB Output is correct
64 Correct 1565 ms 13688 KB Output is correct
65 Correct 919 ms 11688 KB Output is correct
66 Correct 1445 ms 75296 KB Output is correct
67 Correct 1866 ms 104872 KB Output is correct
68 Correct 1543 ms 73368 KB Output is correct
69 Correct 1070 ms 30768 KB Output is correct
70 Correct 1787 ms 90792 KB Output is correct
71 Correct 1810 ms 93488 KB Output is correct
72 Correct 1846 ms 93832 KB Output is correct
73 Correct 1531 ms 73904 KB Output is correct
74 Correct 1529 ms 73812 KB Output is correct
75 Correct 1534 ms 74264 KB Output is correct
76 Correct 1153 ms 37544 KB Output is correct
77 Correct 1125 ms 36524 KB Output is correct
78 Correct 1113 ms 34688 KB Output is correct
79 Correct 934 ms 20860 KB Output is correct
80 Correct 931 ms 19904 KB Output is correct
81 Correct 928 ms 19640 KB Output is correct
82 Correct 896 ms 19160 KB Output is correct
83 Correct 910 ms 18948 KB Output is correct
84 Correct 889 ms 17928 KB Output is correct
85 Correct 2195 ms 80292 KB Output is correct
86 Correct 218 ms 15460 KB Output is correct
87 Correct 141 ms 19812 KB Output is correct
88 Correct 1354 ms 92116 KB Output is correct
89 Correct 2195 ms 78664 KB Output is correct
90 Correct 1358 ms 100844 KB Output is correct
91 Correct 1602 ms 78116 KB Output is correct
92 Correct 1563 ms 77740 KB Output is correct
93 Correct 2276 ms 115712 KB Output is correct
94 Correct 1877 ms 79044 KB Output is correct
95 Correct 1867 ms 79104 KB Output is correct
96 Correct 2279 ms 119792 KB Output is correct
97 Correct 1042 ms 44872 KB Output is correct
98 Correct 1056 ms 41700 KB Output is correct
99 Correct 2234 ms 81052 KB Output is correct
100 Correct 2210 ms 79940 KB Output is correct
101 Correct 2287 ms 79872 KB Output is correct
102 Correct 2250 ms 79972 KB Output is correct
103 Correct 2489 ms 125168 KB Output is correct
104 Correct 2500 ms 124624 KB Output is correct
105 Correct 1817 ms 52440 KB Output is correct
106 Correct 1439 ms 32612 KB Output is correct
107 Correct 1721 ms 59144 KB Output is correct
108 Correct 2328 ms 115220 KB Output is correct
109 Correct 1707 ms 118960 KB Output is correct