oj.uz

Submission #963773

# Submission time Handle Problem Language Result Execution time Memory
963773 2024-04-15T16:02:15 Z oblantis Bridges (APIO19_bridges) C++17
14 / 100
 2220 ms 8832 KB 
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
#define uid(a, b) uniform_int_distribution<int>(a, b)(mt)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
const int mod = 1e9+7;
const int maxn = 1e5+5;
const int sq = 317;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int u[maxn], v[maxn], d[maxn], D[maxn], E[maxn], p[maxn], sz[maxn], a[maxn], b[maxn], wt[maxn];
bool ok[maxn];
bool c(int x, int y){
    return d[x] < d[y];
}
bool cmp(int x, int y){
    return b[x] < b[y];
}
int fnd(int x){
    if(p[x] == x)return x;
    return fnd(p[x]);
}
void solve() {
    int n, m, q;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> u[i] >> v[i] >> d[i];
        --u[i], --v[i];
        E[i] = i;
        D[i] = d[i];
    }
    cin >> q;
    for(int j = 0; j < q; j++){
        cin >> wt[j] >> a[j] >> b[j];
        --a[j];
    }
    vt<int> ch, qu;
    int out[q];
    for(int i = 0; i < q; i += sq){
            ch.clear(), qu.clear();
            for(int j = i; j < q && j / sq == i / sq; j++){
                if(wt[j] == 2){
                    qu.pb(j);
                }
                else {
                    ok[a[j]] = 1;
                    ch.pb(j);
                }
            }
            for(int i = 0; i < n; i++)p[i] = i, sz[i] = 1;
            sort(E, E + m, c);
            sort(all(qu), cmp);
            int sz1 = ch.size(), sz2 = qu.size(), r = m - 1;
            for(int j = sz2 - 1; j >= 0; j--){
                int it = qu[j];
                while(r >= 0 && d[E[r]] >= b[it]){
                    if(!ok[E[r]]){
                        int U = fnd(u[E[r]]), V = fnd(v[E[r]]);
                        if(U != V){
                            if(sz[U] > sz[V])swap(U, V);
                            p[U] = V, sz[V] += sz[U];
                        }
                    }
                    r--;
                }
                for(int o = 0; o < sz1 && ch[o] < it; o++){
                    D[a[ch[o]]] = b[ch[o]];
                }
                vt<pii> rlx;
                for(int o = 0; o < sz1; o++){
                    if(D[a[ch[o]]] >= b[it]){
                        D[a[ch[o]]] = 0;
                        int U = fnd(u[a[ch[o]]]), V = fnd(v[a[ch[o]]]);
                        if(U != V){
                            if(sz[U] > sz[V])swap(U, V);
                            p[U] = V, sz[V] += sz[U];
                            rlx.pb({U, V});
                        }
                    }
                }
                out[it] = sz[fnd(a[it])];
                for(auto j : rlx){
                    p[j.ff] = j.ff;
                    sz[j.ss] -= sz[j.ff];
                }
                for(int o = 0; o < sz1; o++)D[a[ch[o]]] = d[a[ch[o]]];
            }
            for(auto j : ch){
                d[a[j]] = b[j];
            }
    }
    for(int i = 0; i < q; i++){
        if(wt[i] == 2)cout << out[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int times = 1; //cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 14 ms 2804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1381 ms 6616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 893 ms 5920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2199 ms 8824 KB Output is correct
2 Correct 26 ms 4432 KB Output is correct
3 Correct 232 ms 6208 KB Output is correct
4 Correct 159 ms 6228 KB Output is correct
5 Correct 1724 ms 7296 KB Output is correct
6 Correct 2105 ms 8784 KB Output is correct
7 Correct 1728 ms 7288 KB Output is correct
8 Correct 954 ms 6456 KB Output is correct
9 Correct 896 ms 6580 KB Output is correct
10 Correct 933 ms 6568 KB Output is correct
11 Correct 1562 ms 7700 KB Output is correct
12 Correct 1469 ms 7848 KB Output is correct
13 Correct 1550 ms 7204 KB Output is correct
14 Correct 1696 ms 7152 KB Output is correct
15 Correct 1697 ms 7536 KB Output is correct
16 Correct 2211 ms 8748 KB Output is correct
17 Correct 2204 ms 8724 KB Output is correct
18 Correct 2208 ms 8832 KB Output is correct
19 Correct 2220 ms 8824 KB Output is correct
20 Correct 1887 ms 8116 KB Output is correct
21 Correct 1927 ms 8076 KB Output is correct
22 Correct 2133 ms 8748 KB Output is correct
23 Correct 1476 ms 6960 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1381 ms 6616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 14 ms 2804 KB Output isn't correct
4 Halted 0 ms 0 KB -