oj.uz

Submission #934385

# Submission time Handle Problem Language Result Execution time Memory
934385 2024-02-27T09:16:27 Z haxorman Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 29872 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
 
int dsu[mxN], ans[mxN], ind[mxN];
vector<pair<int,pair<int,int>>> add[4 * mxN], edges;
 
int find(int x) {
    return dsu[x] < 0 ? x : find(dsu[x]);
}
 
array<int,3> unite(int x, int y) {
    x = find(x), y = find(y);
 
    if (x == y) return {0, 0, 0};
 
    if (dsu[x] > dsu[y]) {
        swap(x, y);
    }
    array<int,3> rev = {x, y, dsu[y]};
 
    dsu[x] += dsu[y];
    dsu[y] = x;
    return rev;
}
 
void update(int& lo, int& hi, pair<int,pair<int,int>> ed, int ind=1, int l=1, int r=SZ) {
    if (lo > r || l > hi) {
        return;
    }
 
    if (lo <= l && r <= hi) {
        add[ind].push_back(ed);
        return;
    }
 
    int mid = (l + r) / 2;
    update(lo, hi, ed, 2 * ind, l, mid);
    update(lo, hi, ed, 2 * ind + 1, mid + 1, r);
}
 
void query(int& pos, int& node, int& mn, int ind=1, int l=1, int r=SZ) {
    vector<array<int,3>> rem;
    for (auto ed : add[ind]) {
        int w = ed.first;
        auto [u, v] = ed.second;
        //cout << u << ' ' << v << ' ' << w << "\n";
        if (w >= mn) {
            rem.push_back(unite(u, v));

            if (!rem.back()[0]) {
                rem.pop_back();
            }
        }
    }
 
    int mid = (l + r) / 2;
    if (l == r) {
        ans[pos] = -dsu[find(node)];
    }
    else if (pos <= mid) {
        query(pos, node, mn, 2*ind, l, mid);
    }
    else {
        query(pos, node, mn, 2*ind+1, mid+1, r);
    }
 
    for (int i = rem.size() - 1; i >= 0; --i) {
        dsu[rem[i][0]] -= rem[i][2];
        dsu[rem[i][1]] = rem[i][2];
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    memset(dsu, -1, sizeof(dsu));
    int n, m;
    cin >> n >> m;
    
    edges.push_back({0, {0, 0}});
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;

        edges.push_back({w,{u,v}});
        ind[i] = 1;
    }

    int q;
    cin >> q;
    
    vector<pair<int,pair<int,int>>> check;
    for (int i = 1; i <= q; ++i) {
        int t;
        cin >> t;

        if (t == 1) {
            int pos, w;
            cin >> pos >> w;
            
            update(ind[pos], i, edges[pos]);
            edges[pos].first = w;
            ind[pos] = i+1;
        }
        else {
            int node, w;
            cin >> node >> w;

            check.push_back({i, {node, w}});
        }
    }
    
    for (int i = 1; i <= m; ++i) {
        update(ind[i], q, edges[i]);
    }
    
    for (auto que : check) {
        int pos = que.first;
        auto [node, mn] = que.second;
        query(pos, node, mn);
        cout << ans[que.first] << "\n";
    }
}

Compilation message

bridges.cpp: In function 'void query(int&, int&, int&, int, int, int)':
bridges.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         auto [u, v] = ed.second;
      |              ^
bridges.cpp: In function 'int32_t main()':
bridges.cpp:122:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |         auto [node, mn] = que.second;
      |              ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 64 ms 12108 KB Output is correct
4 Correct 6 ms 11292 KB Output is correct
5 Correct 15 ms 11612 KB Output is correct
6 Correct 13 ms 11612 KB Output is correct
7 Correct 16 ms 11800 KB Output is correct
8 Correct 15 ms 11608 KB Output is correct
9 Correct 17 ms 11608 KB Output is correct
10 Correct 16 ms 11612 KB Output is correct
11 Correct 15 ms 11724 KB Output is correct
12 Correct 16 ms 11612 KB Output is correct
13 Correct 19 ms 11868 KB Output is correct
14 Correct 18 ms 11868 KB Output is correct
15 Correct 19 ms 11612 KB Output is correct
16 Correct 16 ms 11740 KB Output is correct
17 Correct 15 ms 11612 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 64 ms 12108 KB Output is correct
4 Correct 6 ms 11292 KB Output is correct
5 Correct 15 ms 11612 KB Output is correct
6 Correct 13 ms 11612 KB Output is correct
7 Correct 16 ms 11800 KB Output is correct
8 Correct 15 ms 11608 KB Output is correct
9 Correct 17 ms 11608 KB Output is correct
10 Correct 16 ms 11612 KB Output is correct
11 Correct 15 ms 11724 KB Output is correct
12 Correct 16 ms 11612 KB Output is correct
13 Correct 19 ms 11868 KB Output is correct
14 Correct 18 ms 11868 KB Output is correct
15 Correct 19 ms 11612 KB Output is correct
16 Correct 16 ms 11740 KB Output is correct
17 Correct 15 ms 11612 KB Output is correct
18 Execution timed out 3059 ms 29872 KB Time limit exceeded
19 Halted 0 ms 0 KB -