oj.uz

Submission #934384

# Submission time Handle Problem Language Result Execution time Memory
934384 2024-02-27T09:16:00 Z haxorman Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 31176 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);
        for (int i = 0; i < mxN; ++i) {
            assert(dsu[i] == -1);
        }
        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 3 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 225 ms 12124 KB Output is correct
4 Correct 334 ms 11540 KB Output is correct
5 Correct 182 ms 11920 KB Output is correct
6 Correct 169 ms 11924 KB Output is correct
7 Correct 170 ms 11836 KB Output is correct
8 Correct 171 ms 11936 KB Output is correct
9 Correct 170 ms 11868 KB Output is correct
10 Correct 172 ms 11932 KB Output is correct
11 Correct 170 ms 11868 KB Output is correct
12 Correct 174 ms 11932 KB Output is correct
13 Correct 179 ms 11980 KB Output is correct
14 Correct 180 ms 12000 KB Output is correct
15 Correct 192 ms 11808 KB Output is correct
16 Correct 173 ms 11868 KB Output is correct
17 Correct 173 ms 11856 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 31176 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 3009 ms 29044 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 3018 ms 25924 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 3084 ms 31176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 225 ms 12124 KB Output is correct
4 Correct 334 ms 11540 KB Output is correct
5 Correct 182 ms 11920 KB Output is correct
6 Correct 169 ms 11924 KB Output is correct
7 Correct 170 ms 11836 KB Output is correct
8 Correct 171 ms 11936 KB Output is correct
9 Correct 170 ms 11868 KB Output is correct
10 Correct 172 ms 11932 KB Output is correct
11 Correct 170 ms 11868 KB Output is correct
12 Correct 174 ms 11932 KB Output is correct
13 Correct 179 ms 11980 KB Output is correct
14 Correct 180 ms 12000 KB Output is correct
15 Correct 192 ms 11808 KB Output is correct
16 Correct 173 ms 11868 KB Output is correct
17 Correct 173 ms 11856 KB Output is correct
18 Execution timed out 3084 ms 31176 KB Time limit exceeded
19 Halted 0 ms 0 KB -