oj.uz

Submission #983203

# Submission time Handle Problem Language Result Execution time Memory
983203 2024-05-15T09:21:13 Z vjudge1 Bridges (APIO19_bridges) C++17
29 / 100
 652 ms 58192 KB 
#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#define ll long long
using namespace std;

int tt = 1, n, m;
ll a[200001], b[200001], c[200001];
vector<pair<int, ll>> g[200005];
ll mn[4 * 200005];
void up(int l, int r, int ind, int num, int v){
    if(l > ind || r < ind) return;
    if(l == r){
        mn[v] = num;
        return;
    }
    int mid = (l + r) / 2;
    up(l, mid, ind, num, v * 2);
    up(mid + 1, r, ind, num, v * 2 + 1);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}
int get_mn(int l, int r, int l1, int r1, int v){
    if(l > r1 || l1 > r) return 1e9;
    if(l >= l1 && r1 >= r) return mn[v];
    int mid = (l + r) / 2;
    return min(get_mn(l, mid, l1, r1, v * 2), get_mn(mid + 1, r, l1, r1, v * 2 + 1));
}
bool us[200005];
bool ok = 0;
pair<ll, pair<int, int>> p[200005], p1[200005];
int cnt[200005], pr[200005], sz[200005];
vector<int> v[200005];
void join(int a, int b){
    a = pr[a];
    b = pr[b];
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    for(int to : v[b])
        pr[to] = a;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    if(n - 1 != m) ok = 1;
    for(int i = 1; i <= m; i++){
        cin >> a[i] >> b[i] >> c[i];
        if(a[i] != i || b[i] != i + 1) ok = 1;
        up(1, m, i, c[i], 1);
        p[i] = {c[i], {a[i], b[i]}};
    }
    for(int i = 1; i <= n; i++){
        pr[i] = i;
        sz[i] = 1;
        v[i].push_back(i);
    }
    cin >> tt;
    if(n <= 1000 && m <= 1000 && tt <= 10000){
        for(int i = 1; i <= tt; i++){
            int type;
            cin >> type;
            if(type == 1){
                ll p, num;
                cin >> p >> num;
                c[p] = num; 
            }
            else{
                ll x, w;
                cin >> x >> w; 
                queue<int> q;
                for(int i = 1; i <= n; i++){
                    g[i].clear();
                    us[i] = 0;
                }
                for(int i = 1; i <= m; i++){
                    g[a[i]].push_back({b[i], c[i]});
                    g[b[i]].push_back({a[i], c[i]});
                }
                q.push(x);
                us[x] = 1;
                int kol = 1;
                while(!q.empty()){
                    int d = q.front();
                    q.pop();
                    for(auto to : g[d]){
                        if(!us[to.first] && to.second >= w){
                            kol++;
                            us[to.first] = 1;
                            q.push(to.first);
                        }
                    }
                }
                cout << kol << "\n";
            }
        }
        return 0;
    }
    if(!ok){
        for(int i = 1; i <= tt; i++){
            int type;
            cin >> type;
            if(type == 1){
                ll p, num;
                cin >> p >> num;
                up(1, m, p, num, 1);
            }
            else{
                ll x, num;
                cin >> x >> num;
                int L = 0, R = x;
                while(L + 1 < R){
                    int mid = (L + R) / 2;
                    if(get_mn(1, m, mid, x - 1, 1) >= num) R = mid;
                    else L = mid;
                }
                int ans = (x - R);
                // cout << ans << "\n";
                L = x - 1, R = n;
                while(L + 1 < R){
                    int mid = (L + R) / 2;
                    if(get_mn(1, m, x, mid, 1) >= num) L = mid;
                    else R = mid;
                }
                ans += (L - x + 1);
                // cout << i << " " << L << "\n";
                cout << ans + 1 << "\n";
            }
        }
        return 0;
    }
    sort(p + 1, p + m + 1);
    for(int i = 1; i <= tt; i++){
        ll type, x, num;
        cin >> type >> x >> num;
        p1[i] = {num, {x, i}};
    }
    sort(p1 + 1, p1 + tt + 1);
    int pos = m;
    for(int i = tt; i >= 1; i++){
        while(pos >= 1 && p[pos].first >= p1[i].first){
            join(p[pos].second.first, p[pos].second.second);
            pos--;
        }
        cnt[p1[i].second.second] = sz[pr[p1[i].second.first]];
    }
    for(int i = 1; i <= tt; i++) cout << cnt[i] << "\n";
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 108 ms 21220 KB Output is correct
4 Correct 6 ms 14940 KB Output is correct
5 Correct 15 ms 21180 KB Output is correct
6 Correct 14 ms 21084 KB Output is correct
7 Correct 16 ms 21164 KB Output is correct
8 Correct 16 ms 21084 KB Output is correct
9 Correct 16 ms 21176 KB Output is correct
10 Correct 15 ms 21084 KB Output is correct
11 Correct 15 ms 21084 KB Output is correct
12 Correct 15 ms 21176 KB Output is correct
13 Correct 21 ms 21080 KB Output is correct
14 Correct 21 ms 21084 KB Output is correct
15 Correct 23 ms 21080 KB Output is correct
16 Correct 15 ms 21080 KB Output is correct
17 Correct 16 ms 21084 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 25028 KB Output is correct
2 Correct 367 ms 24768 KB Output is correct
3 Correct 326 ms 24760 KB Output is correct
4 Correct 353 ms 24840 KB Output is correct
5 Correct 327 ms 24832 KB Output is correct
6 Correct 356 ms 24832 KB Output is correct
7 Correct 364 ms 25104 KB Output is correct
8 Correct 353 ms 24960 KB Output is correct
9 Correct 23 ms 13136 KB Output is correct
10 Correct 326 ms 24912 KB Output is correct
11 Correct 341 ms 24832 KB Output is correct
12 Correct 652 ms 25428 KB Output is correct
13 Correct 124 ms 24668 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 52816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 58192 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 25028 KB Output is correct
2 Correct 367 ms 24768 KB Output is correct
3 Correct 326 ms 24760 KB Output is correct
4 Correct 353 ms 24840 KB Output is correct
5 Correct 327 ms 24832 KB Output is correct
6 Correct 356 ms 24832 KB Output is correct
7 Correct 364 ms 25104 KB Output is correct
8 Correct 353 ms 24960 KB Output is correct
9 Correct 23 ms 13136 KB Output is correct
10 Correct 326 ms 24912 KB Output is correct
11 Correct 341 ms 24832 KB Output is correct
12 Correct 652 ms 25428 KB Output is correct
13 Correct 124 ms 24668 KB Output is correct
14 Runtime error 66 ms 52816 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 108 ms 21220 KB Output is correct
4 Correct 6 ms 14940 KB Output is correct
5 Correct 15 ms 21180 KB Output is correct
6 Correct 14 ms 21084 KB Output is correct
7 Correct 16 ms 21164 KB Output is correct
8 Correct 16 ms 21084 KB Output is correct
9 Correct 16 ms 21176 KB Output is correct
10 Correct 15 ms 21084 KB Output is correct
11 Correct 15 ms 21084 KB Output is correct
12 Correct 15 ms 21176 KB Output is correct
13 Correct 21 ms 21080 KB Output is correct
14 Correct 21 ms 21084 KB Output is correct
15 Correct 23 ms 21080 KB Output is correct
16 Correct 15 ms 21080 KB Output is correct
17 Correct 16 ms 21084 KB Output is correct
18 Correct 325 ms 25028 KB Output is correct
19 Correct 367 ms 24768 KB Output is correct
20 Correct 326 ms 24760 KB Output is correct
21 Correct 353 ms 24840 KB Output is correct
22 Correct 327 ms 24832 KB Output is correct
23 Correct 356 ms 24832 KB Output is correct
24 Correct 364 ms 25104 KB Output is correct
25 Correct 353 ms 24960 KB Output is correct
26 Correct 23 ms 13136 KB Output is correct
27 Correct 326 ms 24912 KB Output is correct
28 Correct 341 ms 24832 KB Output is correct
29 Correct 652 ms 25428 KB Output is correct
30 Correct 124 ms 24668 KB Output is correct
31 Runtime error 66 ms 52816 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -