oj.uz

Submission #716519

# Submission time Handle Problem Language Result Execution time Memory
716519 2023-03-30T08:43:07 Z 1zaid1 Bridges (APIO19_bridges) C++17
16 / 100
 914 ms 115868 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

const int M = 3e6+5, MOD = 998244353;
vector<int> node[M], tmp;
int vis[M], ind[M];

void dfs(int s) {
    vis[s] = true;
    for (auto i:node[s]) {
        if (!vis[i]) dfs(i);
    } tmp.push_back(s);
}

int N = 1 << 20;
int seg[M];

void update(int ind) {
    while (ind /= 2) seg[ind] = min(seg[ind*2], seg[ind*2+1]);
}

int query(int L, int R, int l = 1, int r = N, int ind = 1) {
    if (r < L || l > R) return INT_MAX;
    if (L <= l && r <= R) return seg[ind];
    return min(query(L, R, l, (l+r)/2, ind*2), query(L, R, (l+r)/2+1, r, ind*2+1));
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    for (int &i:seg) i = INT_MAX;

    int n, m;
    cin >> n >> m;

    vector<array<int, 3>> E;
    map<pair<int, int>, int> e;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        node[a].push_back(b);
        node[b].push_back(a);
        E.push_back({a, b, c});
        e[{a, b}] = e[{b, a}] = c;
    }

    int f = 0;
    for (int i = 1; i <= n; i++) if (node[i].size() == 1) f = i;
    dfs(f);
    
    for (int i = 0; i < n-1; i++) {
        seg[i+N] = e[{tmp[i], tmp[i+1]}];
        update(i+N);
    }

    for (int i = 0; i < n; i++) ind[tmp[i]] = i;
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x;

        if (x == 1) {
            cin >> x >> y;
            auto [a, b, c] = E[x-1];
            seg[min(ind[a], ind[b])+N] = y;
            update(min(ind[a], ind[b]) + N);
        } else {
            cin >> x >> y;

            int ans = 1;
            if (ind[x] != n-1) {
                int l = -1, p = (1<<20);
                while (p /= 2) {
                    if (ind[x]+l+p+1 >= n) continue;
                    if (query(ind[x]+1, ind[x]+l+p+1) >= y) l += p;
                } ans += l+1;
            }

            if (ind[x]) {
                int l = 0, p = (1<<20);
                while (p /= 2) {
                    if (ind[x]-(l+p) < 0) continue;
                    if (query(ind[x]-(l+p)+1, ind[x]) >= y) l += p;
                } ans += l;
            }

            cout << ans << endl;
        }
    }

    return 0;
}
/*
5 4
1 3 1
3 5 2
5 4 3
4 2 1
-1
2 2 2

*/

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 107400 KB Output is correct
2 Correct 427 ms 107368 KB Output is correct
3 Correct 431 ms 107388 KB Output is correct
4 Correct 433 ms 107376 KB Output is correct
5 Correct 443 ms 107412 KB Output is correct
6 Correct 437 ms 108656 KB Output is correct
7 Correct 457 ms 110096 KB Output is correct
8 Correct 448 ms 110120 KB Output is correct
9 Correct 71 ms 95696 KB Output is correct
10 Correct 382 ms 109064 KB Output is correct
11 Correct 395 ms 109056 KB Output is correct
12 Correct 720 ms 110300 KB Output is correct
13 Correct 200 ms 110084 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 107400 KB Output is correct
2 Correct 427 ms 107368 KB Output is correct
3 Correct 431 ms 107388 KB Output is correct
4 Correct 433 ms 107376 KB Output is correct
5 Correct 443 ms 107412 KB Output is correct
6 Correct 437 ms 108656 KB Output is correct
7 Correct 457 ms 110096 KB Output is correct
8 Correct 448 ms 110120 KB Output is correct
9 Correct 71 ms 95696 KB Output is correct
10 Correct 382 ms 109064 KB Output is correct
11 Correct 395 ms 109056 KB Output is correct
12 Correct 720 ms 110300 KB Output is correct
13 Correct 200 ms 110084 KB Output is correct
14 Incorrect 388 ms 102264 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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