oj.uz

Submission #963932

# Submission time Handle Problem Language Result Execution time Memory
963932 2024-04-16T04:13:44 Z oblantis Bridges (APIO19_bridges) C++17
14 / 100
 2510 ms 8836 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]];
                }
                stack<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.push({U, V});
                        }
                    }
                }
                out[it] = sz[fnd(a[it])];
                while(!rlx.empty()){
                    pii j = rlx.top();
                    p[j.ff] = j.ff;
                    sz[j.ss] -= sz[j.ff];
                    rlx.pop();
                }
                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 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 12 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1512 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 965 ms 5928 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 2407 ms 8828 KB Output is correct
2 Correct 29 ms 4440 KB Output is correct
3 Correct 241 ms 6212 KB Output is correct
4 Correct 191 ms 6328 KB Output is correct
5 Correct 1897 ms 7296 KB Output is correct
6 Correct 2363 ms 8836 KB Output is correct
7 Correct 1864 ms 7292 KB Output is correct
8 Correct 1004 ms 6460 KB Output is correct
9 Correct 1002 ms 6740 KB Output is correct
10 Correct 1014 ms 6568 KB Output is correct
11 Correct 1705 ms 7704 KB Output is correct
12 Correct 1739 ms 7848 KB Output is correct
13 Correct 1732 ms 7580 KB Output is correct
14 Correct 1801 ms 7560 KB Output is correct
15 Correct 1887 ms 7536 KB Output is correct
16 Correct 2405 ms 8744 KB Output is correct
17 Correct 2510 ms 8740 KB Output is correct
18 Correct 2425 ms 8832 KB Output is correct
19 Correct 2440 ms 8828 KB Output is correct
20 Correct 2097 ms 8120 KB Output is correct
21 Correct 2151 ms 8076 KB Output is correct
22 Correct 2398 ms 8748 KB Output is correct
23 Correct 1603 ms 6968 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1512 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 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 12 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -