oj.uz

Submission #638920

# Submission time Handle Problem Language Result Execution time Memory
638920 2022-09-08T01:24:10 Z BackNoob Bridges (APIO19_bridges) C++14
100 / 100
 2472 ms 10380 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
/*
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
*/

const int mxN = 1e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
const int block = 1000;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

struct DSU{
    int n;
    vector<int> lab;
    vector<pair<int*, int>> trace;

    DSU(){}
    DSU(int _n)
    {
        n = _n;
        lab.resize(n + 7, -1);
    }

    int root(int u) {return lab[u] < 0 ? u : root(lab[u]);}

    void rollback(int idx)
    {
        for(; sz(trace) > idx; trace.pop_back()) {
            *trace.back().fi = trace.back().se;
        }
    }
    void change(int &a, int b)
    {
        trace.pb({&a, a});
        a = b;
    }

    bool union_root(int u, int v)
    {
        u = root(u);
        v = root(v);
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        change(lab[u], lab[v] + lab[u]);
        change(lab[v], u);
        return true;
    }
    int getnow()
    {
        return sz(trace);
    }
} dsu;

struct EDGE{
    int u, v, w;
} ed[mxN];

struct QUERY{
    int op, x, y;
} query[mxN];

struct item{
    int x, y, idx;
    bool operator<(const item &a) const {
        return y > a.y;
    }
};

bool cmp(int &a, int &b)
{
    return ed[a].w > ed[b].w;
}

int n;
int m;
int q;
int neww[mxN];
int ans[mxN];
bool changed[mxN];


void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        ed[i] = {u, v, c};
    }
    cin >> q;
    for(int i = 1; i <= q; i++) cin >> query[i].op >> query[i].x >> query[i].y;

    dsu = DSU(n);
    for(int lef = 1; lef <= q; lef += block) {
        int rig = min(q, lef + block - 1);

        vector<item> calc;
        for(int j = lef; j <= rig; j++) {
            if(query[j].op == 1) {
                changed[query[j].x] = true;
            }
            else {
                calc.pb({query[j].x, query[j].y, j});
            }
        }

        sort(all(calc));

        vector<int> upd;
        vector<int> spec;
        for(int j = 1; j <= m; j++) {
            if(changed[j] == false) upd.pb(j);
            else spec.pb(j);
            changed[j] = false;
        }

        sort(all(upd), cmp);

        dsu.rollback(0);
        int p = 0;
        for(auto it : calc) {
            while(p < sz(upd) && ed[upd[p]].w >= it.y) {
                dsu.union_root(ed[upd[p]].u, ed[upd[p]].v);
                ++p;
            }
            int keep = dsu.getnow();
            for(auto jt : spec) neww[jt] = ed[jt].w;
            for(int j = lef; j <= it.idx; j++) {
                if(query[j].op == 1) {
                    neww[query[j].x] = query[j].y;
                }
            }
            for(auto jt : spec) if(neww[jt] >= it.y) dsu.union_root(ed[jt].u, ed[jt].v);
            ans[it.idx] = -dsu.lab[dsu.root(it.x)];
            dsu.rollback(keep);
        }

        for(int j = lef; j <= rig; j++) {
            if(query[j].op == 1) {
                ed[query[j].x].w = query[j].y;
            }
        }
    }

    for(int i = 1; i <= q; i++) if(query[i].op == 2) cout << ans[i] << endl;

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);


    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 31 ms 468 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 13 ms 468 KB Output is correct
6 Correct 13 ms 468 KB Output is correct
7 Correct 15 ms 516 KB Output is correct
8 Correct 15 ms 504 KB Output is correct
9 Correct 20 ms 468 KB Output is correct
10 Correct 17 ms 512 KB Output is correct
11 Correct 17 ms 508 KB Output is correct
12 Correct 21 ms 532 KB Output is correct
13 Correct 22 ms 504 KB Output is correct
14 Correct 19 ms 520 KB Output is correct
15 Correct 17 ms 488 KB Output is correct
16 Correct 17 ms 512 KB Output is correct
17 Correct 17 ms 528 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1380 ms 5208 KB Output is correct
2 Correct 1413 ms 5216 KB Output is correct
3 Correct 1392 ms 5264 KB Output is correct
4 Correct 1367 ms 5052 KB Output is correct
5 Correct 1356 ms 5024 KB Output is correct
6 Correct 1800 ms 5308 KB Output is correct
7 Correct 1824 ms 7876 KB Output is correct
8 Correct 1797 ms 8092 KB Output is correct
9 Correct 81 ms 3404 KB Output is correct
10 Correct 1039 ms 6880 KB Output is correct
11 Correct 1012 ms 6664 KB Output is correct
12 Correct 1293 ms 7892 KB Output is correct
13 Correct 1162 ms 7664 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1050 ms 4212 KB Output is correct
2 Correct 714 ms 2712 KB Output is correct
3 Correct 1158 ms 4260 KB Output is correct
4 Correct 1038 ms 4108 KB Output is correct
5 Correct 81 ms 2076 KB Output is correct
6 Correct 1129 ms 4072 KB Output is correct
7 Correct 992 ms 4148 KB Output is correct
8 Correct 909 ms 4004 KB Output is correct
9 Correct 793 ms 4228 KB Output is correct
10 Correct 782 ms 4068 KB Output is correct
11 Correct 755 ms 4092 KB Output is correct
12 Correct 675 ms 4008 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1952 ms 6264 KB Output is correct
2 Correct 87 ms 3416 KB Output is correct
3 Correct 191 ms 4528 KB Output is correct
4 Correct 97 ms 4656 KB Output is correct
5 Correct 984 ms 8720 KB Output is correct
6 Correct 1874 ms 10020 KB Output is correct
7 Correct 939 ms 8616 KB Output is correct
8 Correct 951 ms 7592 KB Output is correct
9 Correct 918 ms 7680 KB Output is correct
10 Correct 929 ms 7540 KB Output is correct
11 Correct 1433 ms 9104 KB Output is correct
12 Correct 1396 ms 9300 KB Output is correct
13 Correct 1435 ms 8984 KB Output is correct
14 Correct 879 ms 8956 KB Output is correct
15 Correct 914 ms 8600 KB Output is correct
16 Correct 1915 ms 9964 KB Output is correct
17 Correct 1906 ms 9900 KB Output is correct
18 Correct 1932 ms 10084 KB Output is correct
19 Correct 1906 ms 10096 KB Output is correct
20 Correct 1589 ms 9196 KB Output is correct
21 Correct 1660 ms 9200 KB Output is correct
22 Correct 1911 ms 9888 KB Output is correct
23 Correct 1074 ms 7976 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1380 ms 5208 KB Output is correct
2 Correct 1413 ms 5216 KB Output is correct
3 Correct 1392 ms 5264 KB Output is correct
4 Correct 1367 ms 5052 KB Output is correct
5 Correct 1356 ms 5024 KB Output is correct
6 Correct 1800 ms 5308 KB Output is correct
7 Correct 1824 ms 7876 KB Output is correct
8 Correct 1797 ms 8092 KB Output is correct
9 Correct 81 ms 3404 KB Output is correct
10 Correct 1039 ms 6880 KB Output is correct
11 Correct 1012 ms 6664 KB Output is correct
12 Correct 1293 ms 7892 KB Output is correct
13 Correct 1162 ms 7664 KB Output is correct
14 Correct 1050 ms 4212 KB Output is correct
15 Correct 714 ms 2712 KB Output is correct
16 Correct 1158 ms 4260 KB Output is correct
17 Correct 1038 ms 4108 KB Output is correct
18 Correct 81 ms 2076 KB Output is correct
19 Correct 1129 ms 4072 KB Output is correct
20 Correct 992 ms 4148 KB Output is correct
21 Correct 909 ms 4004 KB Output is correct
22 Correct 793 ms 4228 KB Output is correct
23 Correct 782 ms 4068 KB Output is correct
24 Correct 755 ms 4092 KB Output is correct
25 Correct 675 ms 4008 KB Output is correct
26 Correct 1457 ms 7840 KB Output is correct
27 Correct 1714 ms 7852 KB Output is correct
28 Correct 1527 ms 7880 KB Output is correct
29 Correct 1305 ms 7712 KB Output is correct
30 Correct 1718 ms 7636 KB Output is correct
31 Correct 1690 ms 7732 KB Output is correct
32 Correct 1695 ms 7620 KB Output is correct
33 Correct 1553 ms 7944 KB Output is correct
34 Correct 1537 ms 7780 KB Output is correct
35 Correct 1552 ms 7908 KB Output is correct
36 Correct 1291 ms 7796 KB Output is correct
37 Correct 1250 ms 7876 KB Output is correct
38 Correct 1276 ms 7792 KB Output is correct
39 Correct 1089 ms 7824 KB Output is correct
40 Correct 1091 ms 7828 KB Output is correct
41 Correct 1102 ms 7852 KB Output is correct
42 Correct 1050 ms 7792 KB Output is correct
43 Correct 1054 ms 7656 KB Output is correct
44 Correct 1027 ms 7584 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 31 ms 468 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 13 ms 468 KB Output is correct
6 Correct 13 ms 468 KB Output is correct
7 Correct 15 ms 516 KB Output is correct
8 Correct 15 ms 504 KB Output is correct
9 Correct 20 ms 468 KB Output is correct
10 Correct 17 ms 512 KB Output is correct
11 Correct 17 ms 508 KB Output is correct
12 Correct 21 ms 532 KB Output is correct
13 Correct 22 ms 504 KB Output is correct
14 Correct 19 ms 520 KB Output is correct
15 Correct 17 ms 488 KB Output is correct
16 Correct 17 ms 512 KB Output is correct
17 Correct 17 ms 528 KB Output is correct
18 Correct 1380 ms 5208 KB Output is correct
19 Correct 1413 ms 5216 KB Output is correct
20 Correct 1392 ms 5264 KB Output is correct
21 Correct 1367 ms 5052 KB Output is correct
22 Correct 1356 ms 5024 KB Output is correct
23 Correct 1800 ms 5308 KB Output is correct
24 Correct 1824 ms 7876 KB Output is correct
25 Correct 1797 ms 8092 KB Output is correct
26 Correct 81 ms 3404 KB Output is correct
27 Correct 1039 ms 6880 KB Output is correct
28 Correct 1012 ms 6664 KB Output is correct
29 Correct 1293 ms 7892 KB Output is correct
30 Correct 1162 ms 7664 KB Output is correct
31 Correct 1050 ms 4212 KB Output is correct
32 Correct 714 ms 2712 KB Output is correct
33 Correct 1158 ms 4260 KB Output is correct
34 Correct 1038 ms 4108 KB Output is correct
35 Correct 81 ms 2076 KB Output is correct
36 Correct 1129 ms 4072 KB Output is correct
37 Correct 992 ms 4148 KB Output is correct
38 Correct 909 ms 4004 KB Output is correct
39 Correct 793 ms 4228 KB Output is correct
40 Correct 782 ms 4068 KB Output is correct
41 Correct 755 ms 4092 KB Output is correct
42 Correct 675 ms 4008 KB Output is correct
43 Correct 1952 ms 6264 KB Output is correct
44 Correct 87 ms 3416 KB Output is correct
45 Correct 191 ms 4528 KB Output is correct
46 Correct 97 ms 4656 KB Output is correct
47 Correct 984 ms 8720 KB Output is correct
48 Correct 1874 ms 10020 KB Output is correct
49 Correct 939 ms 8616 KB Output is correct
50 Correct 951 ms 7592 KB Output is correct
51 Correct 918 ms 7680 KB Output is correct
52 Correct 929 ms 7540 KB Output is correct
53 Correct 1433 ms 9104 KB Output is correct
54 Correct 1396 ms 9300 KB Output is correct
55 Correct 1435 ms 8984 KB Output is correct
56 Correct 879 ms 8956 KB Output is correct
57 Correct 914 ms 8600 KB Output is correct
58 Correct 1915 ms 9964 KB Output is correct
59 Correct 1906 ms 9900 KB Output is correct
60 Correct 1932 ms 10084 KB Output is correct
61 Correct 1906 ms 10096 KB Output is correct
62 Correct 1589 ms 9196 KB Output is correct
63 Correct 1660 ms 9200 KB Output is correct
64 Correct 1911 ms 9888 KB Output is correct
65 Correct 1074 ms 7976 KB Output is correct
66 Correct 1457 ms 7840 KB Output is correct
67 Correct 1714 ms 7852 KB Output is correct
68 Correct 1527 ms 7880 KB Output is correct
69 Correct 1305 ms 7712 KB Output is correct
70 Correct 1718 ms 7636 KB Output is correct
71 Correct 1690 ms 7732 KB Output is correct
72 Correct 1695 ms 7620 KB Output is correct
73 Correct 1553 ms 7944 KB Output is correct
74 Correct 1537 ms 7780 KB Output is correct
75 Correct 1552 ms 7908 KB Output is correct
76 Correct 1291 ms 7796 KB Output is correct
77 Correct 1250 ms 7876 KB Output is correct
78 Correct 1276 ms 7792 KB Output is correct
79 Correct 1089 ms 7824 KB Output is correct
80 Correct 1091 ms 7828 KB Output is correct
81 Correct 1102 ms 7852 KB Output is correct
82 Correct 1050 ms 7792 KB Output is correct
83 Correct 1054 ms 7656 KB Output is correct
84 Correct 1027 ms 7584 KB Output is correct
85 Correct 2472 ms 10188 KB Output is correct
86 Correct 255 ms 4872 KB Output is correct
87 Correct 139 ms 4988 KB Output is correct
88 Correct 1470 ms 8760 KB Output is correct
89 Correct 2471 ms 10272 KB Output is correct
90 Correct 1361 ms 8616 KB Output is correct
91 Correct 1441 ms 7856 KB Output is correct
92 Correct 1445 ms 7820 KB Output is correct
93 Correct 1833 ms 7764 KB Output is correct
94 Correct 1957 ms 8972 KB Output is correct
95 Correct 1953 ms 9116 KB Output is correct
96 Correct 2281 ms 9108 KB Output is correct
97 Correct 1086 ms 8808 KB Output is correct
98 Correct 1108 ms 8376 KB Output is correct
99 Correct 2310 ms 10336 KB Output is correct
100 Correct 2278 ms 10196 KB Output is correct
101 Correct 2431 ms 10380 KB Output is correct
102 Correct 2362 ms 10160 KB Output is correct
103 Correct 2382 ms 9464 KB Output is correct
104 Correct 2362 ms 9276 KB Output is correct
105 Correct 1819 ms 9348 KB Output is correct
106 Correct 1490 ms 9020 KB Output is correct
107 Correct 1792 ms 9444 KB Output is correct
108 Correct 2265 ms 9832 KB Output is correct
109 Correct 1563 ms 8096 KB Output is correct