Submission #158124

#	Time	Username	Problem	Language	Result	Execution time	Memory
158124		PeppaPig	Bridges (APIO19_bridges)	C++14	0 / 100	3008 ms	69360 KiB

bridges

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;
const int B = 320;

struct UnionFindDisjointSet {
    int par[N], sz[N];
    stack<int> S;

    void reset() { iota(par, par+N, 0), fill_n(sz, N, 1); }

    int find(int x) { return x == par[x] ? x : find(par[x]); }

    void unite(int a, int b) {
        a = find(a), b = find(b);
        if(a == b) return;
        if(sz[a] > sz[b]) swap(a, b);
        par[a] = b, sz[b] += sz[a];
        S.emplace(a);
    }

    void rollback(int x) {
        while(S.size() > x) {
            int now = S.top(); S.pop();
            sz[par[now]] -= sz[now];
            par[now] = now;
        }
    }
} dsu;

int n, m, q, ans[N];
int u[N], v[N], w[N], t[N], x[N], y[N];
bool chk[N];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) scanf("%d %d %d", u+i, v+i, w+i);
    scanf("%d", &q);
    for(int i = 1; i <= q; i++) scanf("%d %d %d", t+i, x+i, y+i);

    for(int l = 1, r; l <= q; l += B) {
        r = min(q, l + B - 1);
        dsu.reset();
        memset(chk, 0, sizeof chk);

        vector<pii> upd, pre, ask;
        for(int i = l; i <= r; i++) {
            if(t[i] == 1) {
                upd.emplace_back(y[i], i);
                pre.emplace_back(w[x[i]], i);
                chk[x[i]] = true;
            } else ask.emplace_back(y[i], i);
        }
        sort(upd.begin(), upd.end(), greater<pii>());
        sort(pre.begin(), pre.end(), greater<pii>());
        sort(ask.begin(), ask.end(), greater<pii>());

        vector<pii> E;
        for(int i = 1; i <= m; i++) if(!chk[i]) E.emplace_back(w[i], i);
        sort(E.begin(), E.end(), greater<pii>());

        int ptr = 0;
        for(pii p : ask) {
            int idx = x[p.y], cost = y[p.y];
            while(ptr < E.size() && E[ptr].x >= cost)
                dsu.unite(u[E[ptr].y], v[E[ptr].y]), ++ptr;
            int tmp = dsu.S.size();
            for(pii z : upd) if(z.x >= cost && z.y < p.y)
                dsu.unite(u[x[z.y]], v[x[z.y]]);
            for(pii z : pre) if(z.x >= cost && z.y > p.y)
                dsu.unite(u[x[z.y]], v[x[z.y]]);
            ans[p.y] = dsu.sz[dsu.find(idx)];
            dsu.rollback(tmp);
        }
    }
    for(int i = 1; i <= q; i++) if(t[i] == 2) printf("%d\n", ans[i]);

    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void UnionFindDisjointSet::rollback(int)':
bridges.cpp:29:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(S.size() > x) {
                        ^
bridges.cpp: In function 'int main()':
bridges.cpp:71:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(ptr < E.size() && E[ptr].x >= cost)
                   ~~~~^~~~~~~~~~
bridges.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:43:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= m; i++) scanf("%d %d %d", u+i, v+i, w+i);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
bridges.cpp:45:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= q; i++) scanf("%d %d %d", t+i, x+i, y+i);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27