oj.uz

답안 #743916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743916 2023-05-18T06:07:45 Z PixelCat 다리 (APIO19_bridges) C++14
100 / 100
 2886 ms 16012 KB 
/*     code by PixelCat     */
/*         meow owo         */

#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
// using i128 = __int128_t;
using ull = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(998244353)
// #define MOD (int)((LL)1'000'000'007)
#define INF (int)(4e18)
#define EPS (1e-6)

namespace PixelCat {

#ifdef NYAOWO
#include "/home/pixelcat/yodayo/meow/library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod = MOD) {
    int ans = 1;
    for (; p; p >>= 1, b = b * b % mod)
        if (p & 1) ans = ans * b % mod;
    return ans;
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
mt19937_64 rng(
    chrono::steady_clock::now().time_since_epoch().count());

} // namespace PixelCat
using namespace PixelCat;

const int MAXN = 50010;
const int MAXM = 100010;
const int MAXQ = 100010;
const int BLK = 500;

struct DSU {
    int p[MAXN];
    int siz[MAXN];
    vector<pii> op;
    void init() {
        memset(p, 0, sizeof(p));
        fill(siz, siz + MAXN, 1);
        op.clear();
    }
    int find(int n) {
        if(!p[n]) return n;
        return find(p[n]);
    }
    void uni(int a, int b, bool rec = false) {
        a = find(a); b = find(b);
        if(siz[a] < siz[b]) swap(a, b);
        if(rec) op.eb(a, b);
        if(a == b) return;
        p[b] = a;
        siz[a] += siz[b];
    }
    void undo() {
        int a, b;
        tie(a, b) = op.back();
        op.pop_back();
        if(a == b) return;
        siz[a] -= siz[b];
        p[b] = 0;
    }
    void undo_all() {
        while(sz(op)) undo();
    }
    int size(int n) {
        return siz[find(n)];
    }
} dsu;

struct Query {
    int op, x, y;
    // op: 0 for update, 1~q for queries
} qry[MAXQ];
int ans[MAXQ];

pii ed[MAXM];
int w[MAXM];

void solve(int m, int l, int r) {
    // identify bad edges
    // sort good edges
    // sort queries
    vector<pair<pii, int>> e;
    For(i, 1, m) e.eb(ed[i], w[i]);
    vector<int> bad;
    vector<pii> vq;  // {index, weight}
    For(i, l, r) {
        if(!qry[i].op) {
            int eid = qry[i].x;
            e[eid - 1].S = -1;
            bad.eb(eid);
        } else {
            vq.eb(i, qry[i].y);
        }
    }
    sort(all(bad)); bad.erase(unique(all(bad)), bad.end());
    sort(all(e), [&](pair<pii, int> &a, pair<pii, int> &b) {
        return a.S < b.S;
    });
    sort(all(vq), [&](pii &a, pii &b) {
        return a.S < b.S;
    });

    dsu.init();

    // do queries while adding edges
    while(!vq.empty()) {
        int qid = vq.back().F;
        Query &q = qry[qid];
        vq.pop_back();

        // add good edges
        while(sz(e) && e.back().S >= q.y) {
            pii p = e.back().F;
            e.pop_back();
            dsu.uni(p.F, p.S);
        }

        // update bad edges & add to dsu
        For(i, l, qid) if(!qry[i].op) {
            swap(w[qry[i].x], qry[i].y);
        }
        for(int &eid:bad) if(w[eid] >= q.y) {
            dsu.uni(ed[eid].F, ed[eid].S, true);
        }

        // make query
        ans[qid] = dsu.size(q.x);

        // recover bad edges & undo dsu
        dsu.undo_all();
        Forr(i, qid, l) if(!qry[i].op) {
            swap(w[qry[i].x], qry[i].y);
        }
    }

    // actually make updates
    For(i, l, r) if(!qry[i].op) {
        Query &q = qry[i];
        w[q.x] = q.y;
    }
}

int32_t main() {
    NYA();
    // nyaacho >/////<
    int n, m; cin >> n >> m;
    For(i, 1, m) {
        cin >> ed[i].F >> ed[i].S >> w[i];
    }
    int q; cin >> q;
    For(i, 1, q) {
        auto &qr = qry[i];
        cin >> qr.op >> qr.x >> qr.y;
        qr.op--;
    }

    for(int i = 1; i <= q; i += BLK) {
        solve(m, i, min(i + BLK - 1, q));
    }
    For(i, 1, q) if(ans[i]) cout << ans[i] << "\n";
    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 20 ms 1600 KB Output is correct
4 Correct 8 ms 1364 KB Output is correct
5 Correct 13 ms 1464 KB Output is correct
6 Correct 11 ms 1492 KB Output is correct
7 Correct 14 ms 1412 KB Output is correct
8 Correct 13 ms 1436 KB Output is correct
9 Correct 14 ms 1480 KB Output is correct
10 Correct 13 ms 1364 KB Output is correct
11 Correct 14 ms 1428 KB Output is correct
12 Correct 14 ms 1472 KB Output is correct
13 Correct 17 ms 1420 KB Output is correct
14 Correct 16 ms 1456 KB Output is correct
15 Correct 15 ms 1480 KB Output is correct
16 Correct 13 ms 1492 KB Output is correct
17 Correct 13 ms 1492 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1398 ms 8380 KB Output is correct
2 Correct 1440 ms 8348 KB Output is correct
3 Correct 1441 ms 8308 KB Output is correct
4 Correct 1389 ms 8420 KB Output is correct
5 Correct 1461 ms 8372 KB Output is correct
6 Correct 1798 ms 8160 KB Output is correct
7 Correct 1672 ms 8192 KB Output is correct
8 Correct 1741 ms 8148 KB Output is correct
9 Correct 69 ms 4364 KB Output is correct
10 Correct 936 ms 8328 KB Output is correct
11 Correct 1000 ms 8196 KB Output is correct
12 Correct 1515 ms 8268 KB Output is correct
13 Correct 1449 ms 8208 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1060 ms 6640 KB Output is correct
2 Correct 453 ms 4872 KB Output is correct
3 Correct 1097 ms 6672 KB Output is correct
4 Correct 1004 ms 6700 KB Output is correct
5 Correct 78 ms 4388 KB Output is correct
6 Correct 1032 ms 6588 KB Output is correct
7 Correct 965 ms 6592 KB Output is correct
8 Correct 937 ms 6512 KB Output is correct
9 Correct 850 ms 6612 KB Output is correct
10 Correct 892 ms 6564 KB Output is correct
11 Correct 853 ms 6468 KB Output is correct
12 Correct 826 ms 6640 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2846 ms 11988 KB Output is correct
2 Correct 90 ms 5772 KB Output is correct
3 Correct 294 ms 11044 KB Output is correct
4 Correct 148 ms 11160 KB Output is correct
5 Correct 1684 ms 14328 KB Output is correct
6 Correct 2618 ms 15848 KB Output is correct
7 Correct 1670 ms 14284 KB Output is correct
8 Correct 1245 ms 10972 KB Output is correct
9 Correct 1244 ms 11080 KB Output is correct
10 Correct 1281 ms 10700 KB Output is correct
11 Correct 2075 ms 14012 KB Output is correct
12 Correct 1957 ms 14144 KB Output is correct
13 Correct 2134 ms 13996 KB Output is correct
14 Correct 1697 ms 14312 KB Output is correct
15 Correct 1743 ms 14328 KB Output is correct
16 Correct 2635 ms 15976 KB Output is correct
17 Correct 2772 ms 15896 KB Output is correct
18 Correct 2737 ms 15824 KB Output is correct
19 Correct 2587 ms 15800 KB Output is correct
20 Correct 2389 ms 14596 KB Output is correct
21 Correct 2276 ms 14768 KB Output is correct
22 Correct 2614 ms 15492 KB Output is correct
23 Correct 1657 ms 13292 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1398 ms 8380 KB Output is correct
2 Correct 1440 ms 8348 KB Output is correct
3 Correct 1441 ms 8308 KB Output is correct
4 Correct 1389 ms 8420 KB Output is correct
5 Correct 1461 ms 8372 KB Output is correct
6 Correct 1798 ms 8160 KB Output is correct
7 Correct 1672 ms 8192 KB Output is correct
8 Correct 1741 ms 8148 KB Output is correct
9 Correct 69 ms 4364 KB Output is correct
10 Correct 936 ms 8328 KB Output is correct
11 Correct 1000 ms 8196 KB Output is correct
12 Correct 1515 ms 8268 KB Output is correct
13 Correct 1449 ms 8208 KB Output is correct
14 Correct 1060 ms 6640 KB Output is correct
15 Correct 453 ms 4872 KB Output is correct
16 Correct 1097 ms 6672 KB Output is correct
17 Correct 1004 ms 6700 KB Output is correct
18 Correct 78 ms 4388 KB Output is correct
19 Correct 1032 ms 6588 KB Output is correct
20 Correct 965 ms 6592 KB Output is correct
21 Correct 937 ms 6512 KB Output is correct
22 Correct 850 ms 6612 KB Output is correct
23 Correct 892 ms 6564 KB Output is correct
24 Correct 853 ms 6468 KB Output is correct
25 Correct 826 ms 6640 KB Output is correct
26 Correct 1435 ms 8148 KB Output is correct
27 Correct 1678 ms 8268 KB Output is correct
28 Correct 1612 ms 8160 KB Output is correct
29 Correct 1402 ms 8296 KB Output is correct
30 Correct 1543 ms 8180 KB Output is correct
31 Correct 1575 ms 8340 KB Output is correct
32 Correct 1583 ms 8408 KB Output is correct
33 Correct 1507 ms 8124 KB Output is correct
34 Correct 1539 ms 8196 KB Output is correct
35 Correct 1572 ms 8152 KB Output is correct
36 Correct 1357 ms 8188 KB Output is correct
37 Correct 1398 ms 8260 KB Output is correct
38 Correct 1353 ms 8140 KB Output is correct
39 Correct 1326 ms 8336 KB Output is correct
40 Correct 1324 ms 8140 KB Output is correct
41 Correct 1275 ms 8160 KB Output is correct
42 Correct 1200 ms 8272 KB Output is correct
43 Correct 1182 ms 8352 KB Output is correct
44 Correct 1191 ms 8480 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 20 ms 1600 KB Output is correct
4 Correct 8 ms 1364 KB Output is correct
5 Correct 13 ms 1464 KB Output is correct
6 Correct 11 ms 1492 KB Output is correct
7 Correct 14 ms 1412 KB Output is correct
8 Correct 13 ms 1436 KB Output is correct
9 Correct 14 ms 1480 KB Output is correct
10 Correct 13 ms 1364 KB Output is correct
11 Correct 14 ms 1428 KB Output is correct
12 Correct 14 ms 1472 KB Output is correct
13 Correct 17 ms 1420 KB Output is correct
14 Correct 16 ms 1456 KB Output is correct
15 Correct 15 ms 1480 KB Output is correct
16 Correct 13 ms 1492 KB Output is correct
17 Correct 13 ms 1492 KB Output is correct
18 Correct 1398 ms 8380 KB Output is correct
19 Correct 1440 ms 8348 KB Output is correct
20 Correct 1441 ms 8308 KB Output is correct
21 Correct 1389 ms 8420 KB Output is correct
22 Correct 1461 ms 8372 KB Output is correct
23 Correct 1798 ms 8160 KB Output is correct
24 Correct 1672 ms 8192 KB Output is correct
25 Correct 1741 ms 8148 KB Output is correct
26 Correct 69 ms 4364 KB Output is correct
27 Correct 936 ms 8328 KB Output is correct
28 Correct 1000 ms 8196 KB Output is correct
29 Correct 1515 ms 8268 KB Output is correct
30 Correct 1449 ms 8208 KB Output is correct
31 Correct 1060 ms 6640 KB Output is correct
32 Correct 453 ms 4872 KB Output is correct
33 Correct 1097 ms 6672 KB Output is correct
34 Correct 1004 ms 6700 KB Output is correct
35 Correct 78 ms 4388 KB Output is correct
36 Correct 1032 ms 6588 KB Output is correct
37 Correct 965 ms 6592 KB Output is correct
38 Correct 937 ms 6512 KB Output is correct
39 Correct 850 ms 6612 KB Output is correct
40 Correct 892 ms 6564 KB Output is correct
41 Correct 853 ms 6468 KB Output is correct
42 Correct 826 ms 6640 KB Output is correct
43 Correct 2846 ms 11988 KB Output is correct
44 Correct 90 ms 5772 KB Output is correct
45 Correct 294 ms 11044 KB Output is correct
46 Correct 148 ms 11160 KB Output is correct
47 Correct 1684 ms 14328 KB Output is correct
48 Correct 2618 ms 15848 KB Output is correct
49 Correct 1670 ms 14284 KB Output is correct
50 Correct 1245 ms 10972 KB Output is correct
51 Correct 1244 ms 11080 KB Output is correct
52 Correct 1281 ms 10700 KB Output is correct
53 Correct 2075 ms 14012 KB Output is correct
54 Correct 1957 ms 14144 KB Output is correct
55 Correct 2134 ms 13996 KB Output is correct
56 Correct 1697 ms 14312 KB Output is correct
57 Correct 1743 ms 14328 KB Output is correct
58 Correct 2635 ms 15976 KB Output is correct
59 Correct 2772 ms 15896 KB Output is correct
60 Correct 2737 ms 15824 KB Output is correct
61 Correct 2587 ms 15800 KB Output is correct
62 Correct 2389 ms 14596 KB Output is correct
63 Correct 2276 ms 14768 KB Output is correct
64 Correct 2614 ms 15492 KB Output is correct
65 Correct 1657 ms 13292 KB Output is correct
66 Correct 1435 ms 8148 KB Output is correct
67 Correct 1678 ms 8268 KB Output is correct
68 Correct 1612 ms 8160 KB Output is correct
69 Correct 1402 ms 8296 KB Output is correct
70 Correct 1543 ms 8180 KB Output is correct
71 Correct 1575 ms 8340 KB Output is correct
72 Correct 1583 ms 8408 KB Output is correct
73 Correct 1507 ms 8124 KB Output is correct
74 Correct 1539 ms 8196 KB Output is correct
75 Correct 1572 ms 8152 KB Output is correct
76 Correct 1357 ms 8188 KB Output is correct
77 Correct 1398 ms 8260 KB Output is correct
78 Correct 1353 ms 8140 KB Output is correct
79 Correct 1326 ms 8336 KB Output is correct
80 Correct 1324 ms 8140 KB Output is correct
81 Correct 1275 ms 8160 KB Output is correct
82 Correct 1200 ms 8272 KB Output is correct
83 Correct 1182 ms 8352 KB Output is correct
84 Correct 1191 ms 8480 KB Output is correct
85 Correct 2732 ms 15984 KB Output is correct
86 Correct 269 ms 11072 KB Output is correct
87 Correct 163 ms 11216 KB Output is correct
88 Correct 1801 ms 14360 KB Output is correct
89 Correct 2786 ms 15928 KB Output is correct
90 Correct 1782 ms 14488 KB Output is correct
91 Correct 1531 ms 11020 KB Output is correct
92 Correct 1661 ms 11068 KB Output is correct
93 Correct 1824 ms 10740 KB Output is correct
94 Correct 2390 ms 14032 KB Output is correct
95 Correct 2282 ms 14240 KB Output is correct
96 Correct 2367 ms 14168 KB Output is correct
97 Correct 1804 ms 14408 KB Output is correct
98 Correct 1689 ms 14444 KB Output is correct
99 Correct 2855 ms 15980 KB Output is correct
100 Correct 2865 ms 15916 KB Output is correct
101 Correct 2886 ms 16012 KB Output is correct
102 Correct 2826 ms 15872 KB Output is correct
103 Correct 2625 ms 14680 KB Output is correct
104 Correct 2590 ms 14676 KB Output is correct
105 Correct 2301 ms 14632 KB Output is correct
106 Correct 2024 ms 14192 KB Output is correct
107 Correct 2336 ms 14556 KB Output is correct
108 Correct 2751 ms 15408 KB Output is correct
109 Correct 1867 ms 13200 KB Output is correct