oj.uz

Submission #982948

# Submission time Handle Problem Language Result Execution time Memory
982948 2024-05-15T06:01:00 Z angella Bridges (APIO19_bridges) C++17
59 / 100
 3000 ms 37360 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 18, SQ = 320;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, m, q, ev[N], eu[N], ew[N], par[N], sz[N], ans[N], mark[N], ch[N];
vector<int> comp, Q[N], evec[N];
vector<int> qvec[N], rbk;

int getPar(int v) {return (par[v] == 0 ? v : getPar(par[v]));}
void merge(int v, int u) {
    if(getPar(v) == getPar(u)) return;
    v=getPar(v), u=getPar(u);
    if(sz[u] > sz[v]) swap(v,u);
    par[u] = v, sz[v] += sz[u];
    rbk.pb(u);
}
void rolbak(int tmp) {
    while(size(rbk) > tmp) {
        int v = rbk.back(); sz[par[v]] -= sz[v];
        par[v] = 0; rbk.pop_back();
    }
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>ev[i]>>eu[i]>>ew[i]; comp.pb(ew[i]);
    }
    cin>>q;
    for(int typ,x,y,i=1; i<=q; i++) {
        cin>>typ>>x>>y;
        comp.pb(y);
        Q[i] = {typ, x, y};
    }

    sort(all(comp)); comp.resize(unique(all(comp))-comp.begin());
    for(int i=1; i<=m; i++) {
        ew[i] = lower_bound(all(comp),ew[i])-comp.begin()+1;
    }
    for(int i=1; i<=q; i++) {
        Q[i][2] = lower_bound(all(comp),Q[i][2])-comp.begin()+1;
    }

    fill(sz+1, sz+n+1, 1);
    for(int i=1; i<=q; i+=SQ) {
        vector<int> tmp;
        for(int j=i; j<=q&&j<i+SQ; j++) {
            if(Q[j][0] == 1) {
                tmp.pb(j);
                mark[Q[j][1]] = 1;
            } else {
                qvec[Q[j][2]].pb(j);
            }
        }
        for(int j=1; j<=m; j++) {
            if(mark[j]==0) evec[ew[j]].pb(j);
        }
        for(int j=size(comp); j>=1; j--) {
            for(auto it : evec[j]) {
                // cout<<" ~ "<<ev[it]<<' '<<eu[it]<<endl;
                merge(ev[it], eu[it]);
            }
            for(auto it : qvec[j]) {
                for(auto it2 : tmp) {
                if(it2 <= it) ch[Q[it2][1]]=max(ch[Q[it2][1]],it2);
                }
                int rem = size(rbk);
                for(auto it2 : tmp) { 
                    if(ch[Q[it2][1]] >= 0) {
                    
                    if(ch[Q[it2][1]]==0) {
    if(ew[Q[it2][1]]>=Q[it][2])merge(ev[Q[it2][1]],eu[Q[it2][1]]);
                    } else {
    if(Q[ch[Q[it2][1]]][2]>=Q[it][2])merge(ev[Q[it2][1]],eu[Q[it2][1]]);
                    }
                    ch[Q[it2][1]] = -1;
                    
                    }
                }
                for(auto it2 : tmp) ch[Q[it2][1]] = 0;
                // fuck(getPar(Q[it][1]));
                ans[it] = sz[getPar(Q[it][1])];
                rolbak(rem);
            }
        }
        for(int j=i; j<=q&&j<i+SQ; j++) {
            if(Q[j][0] == 1) ew[Q[j][1]] = Q[j][2];
        }
        for(int j=0;j<=max({m,q,(int)size(comp)});j++) {
            par[j]=mark[j]=0, sz[j]=1;
            evec[j].clear(); qvec[j].clear();
        }
        rbk.clear();
    }

    for(int i=1; i<=q; i++) {
        if(ans[i] > 0) cout<<ans[i]<<'\n';
    }

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23140 KB Output is correct
2 Correct 10 ms 23132 KB Output is correct
3 Correct 26 ms 23900 KB Output is correct
4 Correct 16 ms 23816 KB Output is correct
5 Correct 21 ms 23644 KB Output is correct
6 Correct 19 ms 23644 KB Output is correct
7 Correct 19 ms 23644 KB Output is correct
8 Correct 22 ms 23612 KB Output is correct
9 Correct 20 ms 23644 KB Output is correct
10 Correct 22 ms 23756 KB Output is correct
11 Correct 22 ms 23900 KB Output is correct
12 Correct 23 ms 23876 KB Output is correct
13 Correct 24 ms 23900 KB Output is correct
14 Correct 23 ms 23896 KB Output is correct
15 Correct 23 ms 23900 KB Output is correct
16 Correct 21 ms 23644 KB Output is correct
17 Correct 21 ms 23896 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1406 ms 34232 KB Output is correct
2 Correct 1434 ms 34804 KB Output is correct
3 Correct 1407 ms 34056 KB Output is correct
4 Correct 1476 ms 34032 KB Output is correct
5 Correct 1451 ms 34372 KB Output is correct
6 Correct 1349 ms 33632 KB Output is correct
7 Correct 1393 ms 34176 KB Output is correct
8 Correct 1446 ms 34300 KB Output is correct
9 Correct 170 ms 31232 KB Output is correct
10 Correct 439 ms 29388 KB Output is correct
11 Correct 438 ms 29528 KB Output is correct
12 Correct 943 ms 33988 KB Output is correct
13 Correct 1311 ms 34108 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 957 ms 33260 KB Output is correct
2 Correct 423 ms 30664 KB Output is correct
3 Correct 916 ms 32000 KB Output is correct
4 Correct 1006 ms 33124 KB Output is correct
5 Correct 179 ms 31100 KB Output is correct
6 Correct 974 ms 33044 KB Output is correct
7 Correct 994 ms 33136 KB Output is correct
8 Correct 927 ms 33216 KB Output is correct
9 Correct 789 ms 33244 KB Output is correct
10 Correct 848 ms 33260 KB Output is correct
11 Correct 876 ms 32892 KB Output is correct
12 Correct 865 ms 32972 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2853 ms 37360 KB Output is correct
2 Correct 214 ms 32936 KB Output is correct
3 Correct 193 ms 29304 KB Output is correct
4 Correct 111 ms 26508 KB Output is correct
5 Correct 1039 ms 30964 KB Output is correct
6 Correct 2936 ms 37248 KB Output is correct
7 Correct 1066 ms 30956 KB Output is correct
8 Correct 1340 ms 34312 KB Output is correct
9 Correct 1256 ms 34124 KB Output is correct
10 Correct 1041 ms 34452 KB Output is correct
11 Correct 2493 ms 34596 KB Output is correct
12 Correct 2364 ms 34592 KB Output is correct
13 Correct 1707 ms 35924 KB Output is correct
14 Correct 1047 ms 29652 KB Output is correct
15 Correct 1048 ms 29540 KB Output is correct
16 Execution timed out 3067 ms 36676 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1406 ms 34232 KB Output is correct
2 Correct 1434 ms 34804 KB Output is correct
3 Correct 1407 ms 34056 KB Output is correct
4 Correct 1476 ms 34032 KB Output is correct
5 Correct 1451 ms 34372 KB Output is correct
6 Correct 1349 ms 33632 KB Output is correct
7 Correct 1393 ms 34176 KB Output is correct
8 Correct 1446 ms 34300 KB Output is correct
9 Correct 170 ms 31232 KB Output is correct
10 Correct 439 ms 29388 KB Output is correct
11 Correct 438 ms 29528 KB Output is correct
12 Correct 943 ms 33988 KB Output is correct
13 Correct 1311 ms 34108 KB Output is correct
14 Correct 957 ms 33260 KB Output is correct
15 Correct 423 ms 30664 KB Output is correct
16 Correct 916 ms 32000 KB Output is correct
17 Correct 1006 ms 33124 KB Output is correct
18 Correct 179 ms 31100 KB Output is correct
19 Correct 974 ms 33044 KB Output is correct
20 Correct 994 ms 33136 KB Output is correct
21 Correct 927 ms 33216 KB Output is correct
22 Correct 789 ms 33244 KB Output is correct
23 Correct 848 ms 33260 KB Output is correct
24 Correct 876 ms 32892 KB Output is correct
25 Correct 865 ms 32972 KB Output is correct
26 Correct 1587 ms 34160 KB Output is correct
27 Correct 1852 ms 32256 KB Output is correct
28 Correct 1844 ms 33084 KB Output is correct
29 Correct 1561 ms 33052 KB Output is correct
30 Correct 1693 ms 32576 KB Output is correct
31 Correct 1770 ms 32732 KB Output is correct
32 Correct 1894 ms 32472 KB Output is correct
33 Correct 1877 ms 33168 KB Output is correct
34 Correct 1968 ms 33276 KB Output is correct
35 Correct 1535 ms 34004 KB Output is correct
36 Correct 1540 ms 34144 KB Output is correct
37 Correct 1695 ms 34152 KB Output is correct
38 Correct 1630 ms 34176 KB Output is correct
39 Correct 1432 ms 34176 KB Output is correct
40 Correct 1365 ms 34308 KB Output is correct
41 Correct 1280 ms 34352 KB Output is correct
42 Correct 1587 ms 34104 KB Output is correct
43 Correct 1453 ms 34236 KB Output is correct
44 Correct 1802 ms 33924 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23140 KB Output is correct
2 Correct 10 ms 23132 KB Output is correct
3 Correct 26 ms 23900 KB Output is correct
4 Correct 16 ms 23816 KB Output is correct
5 Correct 21 ms 23644 KB Output is correct
6 Correct 19 ms 23644 KB Output is correct
7 Correct 19 ms 23644 KB Output is correct
8 Correct 22 ms 23612 KB Output is correct
9 Correct 20 ms 23644 KB Output is correct
10 Correct 22 ms 23756 KB Output is correct
11 Correct 22 ms 23900 KB Output is correct
12 Correct 23 ms 23876 KB Output is correct
13 Correct 24 ms 23900 KB Output is correct
14 Correct 23 ms 23896 KB Output is correct
15 Correct 23 ms 23900 KB Output is correct
16 Correct 21 ms 23644 KB Output is correct
17 Correct 21 ms 23896 KB Output is correct
18 Correct 1406 ms 34232 KB Output is correct
19 Correct 1434 ms 34804 KB Output is correct
20 Correct 1407 ms 34056 KB Output is correct
21 Correct 1476 ms 34032 KB Output is correct
22 Correct 1451 ms 34372 KB Output is correct
23 Correct 1349 ms 33632 KB Output is correct
24 Correct 1393 ms 34176 KB Output is correct
25 Correct 1446 ms 34300 KB Output is correct
26 Correct 170 ms 31232 KB Output is correct
27 Correct 439 ms 29388 KB Output is correct
28 Correct 438 ms 29528 KB Output is correct
29 Correct 943 ms 33988 KB Output is correct
30 Correct 1311 ms 34108 KB Output is correct
31 Correct 957 ms 33260 KB Output is correct
32 Correct 423 ms 30664 KB Output is correct
33 Correct 916 ms 32000 KB Output is correct
34 Correct 1006 ms 33124 KB Output is correct
35 Correct 179 ms 31100 KB Output is correct
36 Correct 974 ms 33044 KB Output is correct
37 Correct 994 ms 33136 KB Output is correct
38 Correct 927 ms 33216 KB Output is correct
39 Correct 789 ms 33244 KB Output is correct
40 Correct 848 ms 33260 KB Output is correct
41 Correct 876 ms 32892 KB Output is correct
42 Correct 865 ms 32972 KB Output is correct
43 Correct 2853 ms 37360 KB Output is correct
44 Correct 214 ms 32936 KB Output is correct
45 Correct 193 ms 29304 KB Output is correct
46 Correct 111 ms 26508 KB Output is correct
47 Correct 1039 ms 30964 KB Output is correct
48 Correct 2936 ms 37248 KB Output is correct
49 Correct 1066 ms 30956 KB Output is correct
50 Correct 1340 ms 34312 KB Output is correct
51 Correct 1256 ms 34124 KB Output is correct
52 Correct 1041 ms 34452 KB Output is correct
53 Correct 2493 ms 34596 KB Output is correct
54 Correct 2364 ms 34592 KB Output is correct
55 Correct 1707 ms 35924 KB Output is correct
56 Correct 1047 ms 29652 KB Output is correct
57 Correct 1048 ms 29540 KB Output is correct
58 Execution timed out 3067 ms 36676 KB Time limit exceeded
59 Halted 0 ms 0 KB -