oj.uz

Submission #982952

# Submission time Handle Problem Language Result Execution time Memory
982952 2024-05-15T06:02:41 Z angella Bridges (APIO19_bridges) C++17
59 / 100
 3000 ms 36844 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 = 280;
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 21592 KB Output is correct
2 Correct 10 ms 21596 KB Output is correct
3 Correct 25 ms 22360 KB Output is correct
4 Correct 16 ms 22364 KB Output is correct
5 Correct 22 ms 22108 KB Output is correct
6 Correct 28 ms 22104 KB Output is correct
7 Correct 20 ms 22104 KB Output is correct
8 Correct 22 ms 22108 KB Output is correct
9 Correct 24 ms 22128 KB Output is correct
10 Correct 23 ms 22324 KB Output is correct
11 Correct 23 ms 22104 KB Output is correct
12 Correct 23 ms 22260 KB Output is correct
13 Correct 24 ms 22324 KB Output is correct
14 Correct 28 ms 22200 KB Output is correct
15 Correct 25 ms 22352 KB Output is correct
16 Correct 19 ms 22104 KB Output is correct
17 Correct 27 ms 22148 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1794 ms 33316 KB Output is correct
2 Correct 1664 ms 34072 KB Output is correct
3 Correct 1816 ms 34252 KB Output is correct
4 Correct 2033 ms 34196 KB Output is correct
5 Correct 2128 ms 34212 KB Output is correct
6 Correct 1813 ms 33328 KB Output is correct
7 Correct 1838 ms 33832 KB Output is correct
8 Correct 1763 ms 34084 KB Output is correct
9 Correct 190 ms 30000 KB Output is correct
10 Correct 510 ms 29920 KB Output is correct
11 Correct 494 ms 29564 KB Output is correct
12 Correct 1235 ms 33840 KB Output is correct
13 Correct 1561 ms 33048 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 32036 KB Output is correct
2 Correct 520 ms 29480 KB Output is correct
3 Correct 1126 ms 32468 KB Output is correct
4 Correct 1102 ms 33116 KB Output is correct
5 Correct 194 ms 31156 KB Output is correct
6 Correct 1133 ms 33236 KB Output is correct
7 Correct 1172 ms 32976 KB Output is correct
8 Correct 1091 ms 33008 KB Output is correct
9 Correct 951 ms 33208 KB Output is correct
10 Correct 921 ms 33164 KB Output is correct
11 Correct 974 ms 32832 KB Output is correct
12 Correct 959 ms 32968 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 36844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1794 ms 33316 KB Output is correct
2 Correct 1664 ms 34072 KB Output is correct
3 Correct 1816 ms 34252 KB Output is correct
4 Correct 2033 ms 34196 KB Output is correct
5 Correct 2128 ms 34212 KB Output is correct
6 Correct 1813 ms 33328 KB Output is correct
7 Correct 1838 ms 33832 KB Output is correct
8 Correct 1763 ms 34084 KB Output is correct
9 Correct 190 ms 30000 KB Output is correct
10 Correct 510 ms 29920 KB Output is correct
11 Correct 494 ms 29564 KB Output is correct
12 Correct 1235 ms 33840 KB Output is correct
13 Correct 1561 ms 33048 KB Output is correct
14 Correct 1139 ms 32036 KB Output is correct
15 Correct 520 ms 29480 KB Output is correct
16 Correct 1126 ms 32468 KB Output is correct
17 Correct 1102 ms 33116 KB Output is correct
18 Correct 194 ms 31156 KB Output is correct
19 Correct 1133 ms 33236 KB Output is correct
20 Correct 1172 ms 32976 KB Output is correct
21 Correct 1091 ms 33008 KB Output is correct
22 Correct 951 ms 33208 KB Output is correct
23 Correct 921 ms 33164 KB Output is correct
24 Correct 974 ms 32832 KB Output is correct
25 Correct 959 ms 32968 KB Output is correct
26 Correct 1619 ms 34228 KB Output is correct
27 Correct 1649 ms 33076 KB Output is correct
28 Correct 1728 ms 34132 KB Output is correct
29 Correct 1615 ms 34116 KB Output is correct
30 Correct 1643 ms 33744 KB Output is correct
31 Correct 1725 ms 33444 KB Output is correct
32 Correct 1629 ms 33536 KB Output is correct
33 Correct 1706 ms 34220 KB Output is correct
34 Correct 1665 ms 34436 KB Output is correct
35 Correct 1707 ms 34020 KB Output is correct
36 Correct 1626 ms 34072 KB Output is correct
37 Correct 1660 ms 34104 KB Output is correct
38 Correct 1607 ms 34108 KB Output is correct
39 Correct 1445 ms 34492 KB Output is correct
40 Correct 1458 ms 34180 KB Output is correct
41 Correct 1445 ms 34280 KB Output is correct
42 Correct 1586 ms 34192 KB Output is correct
43 Correct 1690 ms 34420 KB Output is correct
44 Correct 1651 ms 34164 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21592 KB Output is correct
2 Correct 10 ms 21596 KB Output is correct
3 Correct 25 ms 22360 KB Output is correct
4 Correct 16 ms 22364 KB Output is correct
5 Correct 22 ms 22108 KB Output is correct
6 Correct 28 ms 22104 KB Output is correct
7 Correct 20 ms 22104 KB Output is correct
8 Correct 22 ms 22108 KB Output is correct
9 Correct 24 ms 22128 KB Output is correct
10 Correct 23 ms 22324 KB Output is correct
11 Correct 23 ms 22104 KB Output is correct
12 Correct 23 ms 22260 KB Output is correct
13 Correct 24 ms 22324 KB Output is correct
14 Correct 28 ms 22200 KB Output is correct
15 Correct 25 ms 22352 KB Output is correct
16 Correct 19 ms 22104 KB Output is correct
17 Correct 27 ms 22148 KB Output is correct
18 Correct 1794 ms 33316 KB Output is correct
19 Correct 1664 ms 34072 KB Output is correct
20 Correct 1816 ms 34252 KB Output is correct
21 Correct 2033 ms 34196 KB Output is correct
22 Correct 2128 ms 34212 KB Output is correct
23 Correct 1813 ms 33328 KB Output is correct
24 Correct 1838 ms 33832 KB Output is correct
25 Correct 1763 ms 34084 KB Output is correct
26 Correct 190 ms 30000 KB Output is correct
27 Correct 510 ms 29920 KB Output is correct
28 Correct 494 ms 29564 KB Output is correct
29 Correct 1235 ms 33840 KB Output is correct
30 Correct 1561 ms 33048 KB Output is correct
31 Correct 1139 ms 32036 KB Output is correct
32 Correct 520 ms 29480 KB Output is correct
33 Correct 1126 ms 32468 KB Output is correct
34 Correct 1102 ms 33116 KB Output is correct
35 Correct 194 ms 31156 KB Output is correct
36 Correct 1133 ms 33236 KB Output is correct
37 Correct 1172 ms 32976 KB Output is correct
38 Correct 1091 ms 33008 KB Output is correct
39 Correct 951 ms 33208 KB Output is correct
40 Correct 921 ms 33164 KB Output is correct
41 Correct 974 ms 32832 KB Output is correct
42 Correct 959 ms 32968 KB Output is correct
43 Execution timed out 3039 ms 36844 KB Time limit exceeded
44 Halted 0 ms 0 KB -