Submission #355432

#	Time	Username	Problem	Language	Result	Execution time	Memory
355432		parsabahrami	Bridges (APIO19_bridges)	C++17	100 / 100	2836 ms	111272 KiB

bridges

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e4 + 5, SQ = 700;
int P[N], S[N], ret[N * 2], M[N * 2], W[N * 2], U[N * 2], V[N * 2], t[N * 2], X[N * 2], Y[N * 2], n, q, m;
vector<pii> hist; vector<int> vec[N * 2], ask, upd, gd;

int Find(int v) {
    return !P[v] ? v : Find(P[v]);
}

int Union(int u, int v) {
    u = Find(u), v = Find(v);
    if (u == v) return 0;
    if (S[u] > S[v]) swap(u, v);
    hist.push_back({v, u});
    P[u] = v, S[v] += S[u];
    return 1;  
}

void Undo(int C) {
    while (C--) {
        int u, v; tie(v, u) = hist.back(); hist.pop_back();
        P[u] = 0, S[v] -= S[u];
    }
}

int main() {
    fill(S, S + N, 1);
    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; l <= q; l += SQ) {
        int r = min(q, l + SQ - 1);
        Undo(SZ(hist));
        memset(M, 0, sizeof M); 
        upd = ask = gd = {};
        for (int i = l; i <= r; i++) {
            if (t[i] == 1) {
                M[X[i]] = 1;
                upd.push_back(i);
            } else {
                ask.push_back(i);
            }
        }
        for (int i = 1; i <= m; i++) {
            if (!M[i]) gd.push_back(i);
        }
        for (int i = l; i <= r; i++) {
            if (t[i] == 1) {
                W[X[i]] = Y[i];
            } else {
                for (int j : upd) if (W[X[j]] >= Y[i]) vec[i].push_back(X[j]);
            }
        }
        sort(ask.begin(), ask.end(), [&] (int u, int v) { return Y[u] > Y[v]; });
        sort(gd.begin(), gd.end(), [&] (int u, int v) { return W[u] > W[v]; });
        int ptr = 0;
        for (int &i : ask) {
            while (ptr < SZ(gd) && W[gd[ptr]] >= Y[i]) Union(U[gd[ptr]], V[gd[ptr]]), ptr++;
            int C = 0;
            for (int &j : vec[i]) C += Union(U[j], V[j]);
            ret[i] = S[Find(X[i])];
            Undo(C);
        }
    }
    for (int i = 1; i <= q; i++) if (t[i] == 2) printf("%d\n", ret[i]);
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d%d%d", &U[i], &V[i], &W[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:44:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |     for (int i = 1; i <= q; i++) scanf("%d%d%d", &t[i], &X[i], &Y[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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