oj.uz

Submission #535960

# Submission time Handle Problem Language Result Execution time Memory
535960 2022-03-12T00:29:06 Z Evang Bridges (APIO19_bridges) C++17
100 / 100
 1923 ms 131244 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int bsz = 1000;
const int M = 1e5+5;
const int Q = M;
int n, m, q, t[Q], x[Q], y[Q], ans[Q];
struct edge {
    int v, u, w;
} e[M];
vi to_join[Q];

struct dsu {
    vi lk, sz, un;
    dsu(int n){
        lk.resize(n);
        sz.resize(n);
        iota(all(lk), 0);
        fill(all(sz), 1);
    }
    int root(int a){
        while(a^lk[a])
            a = lk[a];
        return a;
    }
    void join(int a, int b){
        a = root(a);
        b = root(b);
        if(a==b)
            return;

        if(sz[a]<sz[b])
            swap(a, b);

        un.pb(b);
        lk[b] = a;
        sz[a] += sz[b];
    }
    void undo(){
        int b = un.back();
        sz[lk[b]] -= sz[b];
        lk[b] = b;
        un.pop_back();
    }
    void undo(int x){
        while(ssize(un)>x)
            undo();
    }
};

struct bset {
    bitset<M> b;
    vi op;
    void set(int i){
        if(b[i])
            return;
        op.pb(i);
        b[i] = 1;
    }
    bool at(int i){
        return b[i];
    }
    void clear(){
        while(!op.empty()){
            b[op.back()] = 0;
            op.pop_back();
        }
    }
} changed, bset;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
        cin >> e[i].v >> e[i].u >> e[i].w;

    cin >> q;
    for(int i = 0; i < q; ++i) {
        cin >> t[i] >> x[i] >> y[i];
        // if t[i] == 1, then:
        //     bridge x[i] now has weight y[i]
        // else
        //     car with weight y[i] is on node x[i]
    }

    for(int l = 0; l < q; l += bsz){
        int r = min(l + bsz, q);
        changed.clear();
        vi ask, upd;
        for(int i = l; i < r; ++i) {
            if (t[i] == 1) {
                changed.set(x[i]);
                upd.pb(i);
            }else
                ask.pb(i);
        }
        for(int i = l; i < r; ++i){
            if(t[i]==1)
                e[x[i]].w = y[i];
            else {
                to_join[i].clear();
                for (int j: upd)
                    if(e[x[j]].w >= y[i])
                        to_join[i].pb(x[j]);
            }
        }
        sort(all(ask), [](int i, int j){
            return y[i] > y[j];
        });

        vc<edge> unchanged;
        for(int i = 1; i <= m; ++i)
            if(!changed.at(i))
                unchanged.pb(e[i]);
        sort(all(unchanged), [](edge a, edge b){
            return a.w < b.w;
        });

        dsu d(n+1);
        for(int i: ask){
            while(!unchanged.empty()&&unchanged.back().w>=y[i]) {
                d.join(unchanged.back().v, unchanged.back().u);
                unchanged.pop_back();
            }

            int prev_size = ssize(d.un);
            for(int j: to_join[i])
                d.join(e[j].v, e[j].u);
//            bset.clear();
//            for(int k = p; k >= 0; --k) {
//                int j = upd[k];
//                if (!bset.at(x[j])) {
//                    bset.set(x[j]);
//                    if (y[j] >= y[i])
//                        d.join(e[x[j]].v, e[x[j]].u);
//                }
//            }
//
//            for(int k = p+1; k < ssize(upd); ++k) {
//                int j = upd[k];
//                if (!bset.at(x[j]) && e[x[j]].w >= y[i])
//                    d.join(e[x[j]].v, e[x[j]].u);
//            }

            ans[i] = d.sz[d.root(x[i])];

            d.undo(prev_size);
        }

        for(int i: upd)
            e[x[i]].w = y[i];
    }

    for(int i = 0; i < q; ++i)
        if(t[i]==2)
            cout << ans[i] << el;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 39 ms 9600 KB Output is correct
4 Correct 5 ms 2824 KB Output is correct
5 Correct 39 ms 10196 KB Output is correct
6 Correct 32 ms 10480 KB Output is correct
7 Correct 37 ms 10424 KB Output is correct
8 Correct 41 ms 8828 KB Output is correct
9 Correct 47 ms 14800 KB Output is correct
10 Correct 43 ms 9648 KB Output is correct
11 Correct 42 ms 9420 KB Output is correct
12 Correct 48 ms 12036 KB Output is correct
13 Correct 46 ms 10132 KB Output is correct
14 Correct 44 ms 9272 KB Output is correct
15 Correct 49 ms 10004 KB Output is correct
16 Correct 44 ms 13004 KB Output is correct
17 Correct 45 ms 12012 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1227 ms 73444 KB Output is correct
2 Correct 1233 ms 73368 KB Output is correct
3 Correct 1235 ms 73664 KB Output is correct
4 Correct 1286 ms 73232 KB Output is correct
5 Correct 1243 ms 73908 KB Output is correct
6 Correct 1852 ms 131244 KB Output is correct
7 Correct 1912 ms 127704 KB Output is correct
8 Correct 1826 ms 127488 KB Output is correct
9 Correct 41 ms 4460 KB Output is correct
10 Correct 1130 ms 99512 KB Output is correct
11 Correct 1075 ms 98936 KB Output is correct
12 Correct 1002 ms 53392 KB Output is correct
13 Correct 1034 ms 46476 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 73028 KB Output is correct
2 Correct 815 ms 97744 KB Output is correct
3 Correct 1189 ms 100800 KB Output is correct
4 Correct 980 ms 72332 KB Output is correct
5 Correct 36 ms 4424 KB Output is correct
6 Correct 1102 ms 92228 KB Output is correct
7 Correct 876 ms 64536 KB Output is correct
8 Correct 787 ms 48568 KB Output is correct
9 Correct 640 ms 40388 KB Output is correct
10 Correct 574 ms 28776 KB Output is correct
11 Correct 676 ms 38140 KB Output is correct
12 Correct 574 ms 28172 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1258 ms 8148 KB Output is correct
2 Correct 34 ms 5820 KB Output is correct
3 Correct 143 ms 8568 KB Output is correct
4 Correct 103 ms 8756 KB Output is correct
5 Correct 743 ms 10428 KB Output is correct
6 Correct 1195 ms 11988 KB Output is correct
7 Correct 756 ms 10472 KB Output is correct
8 Correct 644 ms 9232 KB Output is correct
9 Correct 613 ms 9260 KB Output is correct
10 Correct 642 ms 8952 KB Output is correct
11 Correct 966 ms 10888 KB Output is correct
12 Correct 978 ms 10968 KB Output is correct
13 Correct 991 ms 10692 KB Output is correct
14 Correct 646 ms 10436 KB Output is correct
15 Correct 704 ms 10488 KB Output is correct
16 Correct 1267 ms 12148 KB Output is correct
17 Correct 1301 ms 12112 KB Output is correct
18 Correct 1257 ms 12036 KB Output is correct
19 Correct 1218 ms 11960 KB Output is correct
20 Correct 1101 ms 10920 KB Output is correct
21 Correct 1062 ms 10900 KB Output is correct
22 Correct 1210 ms 11708 KB Output is correct
23 Correct 752 ms 9804 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1227 ms 73444 KB Output is correct
2 Correct 1233 ms 73368 KB Output is correct
3 Correct 1235 ms 73664 KB Output is correct
4 Correct 1286 ms 73232 KB Output is correct
5 Correct 1243 ms 73908 KB Output is correct
6 Correct 1852 ms 131244 KB Output is correct
7 Correct 1912 ms 127704 KB Output is correct
8 Correct 1826 ms 127488 KB Output is correct
9 Correct 41 ms 4460 KB Output is correct
10 Correct 1130 ms 99512 KB Output is correct
11 Correct 1075 ms 98936 KB Output is correct
12 Correct 1002 ms 53392 KB Output is correct
13 Correct 1034 ms 46476 KB Output is correct
14 Correct 1000 ms 73028 KB Output is correct
15 Correct 815 ms 97744 KB Output is correct
16 Correct 1189 ms 100800 KB Output is correct
17 Correct 980 ms 72332 KB Output is correct
18 Correct 36 ms 4424 KB Output is correct
19 Correct 1102 ms 92228 KB Output is correct
20 Correct 876 ms 64536 KB Output is correct
21 Correct 787 ms 48568 KB Output is correct
22 Correct 640 ms 40388 KB Output is correct
23 Correct 574 ms 28776 KB Output is correct
24 Correct 676 ms 38140 KB Output is correct
25 Correct 574 ms 28172 KB Output is correct
26 Correct 1187 ms 73344 KB Output is correct
27 Correct 1572 ms 102728 KB Output is correct
28 Correct 1284 ms 71692 KB Output is correct
29 Correct 850 ms 28912 KB Output is correct
30 Correct 1460 ms 88996 KB Output is correct
31 Correct 1533 ms 91572 KB Output is correct
32 Correct 1523 ms 91832 KB Output is correct
33 Correct 1242 ms 72184 KB Output is correct
34 Correct 1286 ms 72256 KB Output is correct
35 Correct 1261 ms 72556 KB Output is correct
36 Correct 934 ms 35868 KB Output is correct
37 Correct 944 ms 34392 KB Output is correct
38 Correct 910 ms 32988 KB Output is correct
39 Correct 737 ms 19248 KB Output is correct
40 Correct 730 ms 18032 KB Output is correct
41 Correct 686 ms 17644 KB Output is correct
42 Correct 707 ms 17424 KB Output is correct
43 Correct 731 ms 16824 KB Output is correct
44 Correct 718 ms 16200 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 39 ms 9600 KB Output is correct
4 Correct 5 ms 2824 KB Output is correct
5 Correct 39 ms 10196 KB Output is correct
6 Correct 32 ms 10480 KB Output is correct
7 Correct 37 ms 10424 KB Output is correct
8 Correct 41 ms 8828 KB Output is correct
9 Correct 47 ms 14800 KB Output is correct
10 Correct 43 ms 9648 KB Output is correct
11 Correct 42 ms 9420 KB Output is correct
12 Correct 48 ms 12036 KB Output is correct
13 Correct 46 ms 10132 KB Output is correct
14 Correct 44 ms 9272 KB Output is correct
15 Correct 49 ms 10004 KB Output is correct
16 Correct 44 ms 13004 KB Output is correct
17 Correct 45 ms 12012 KB Output is correct
18 Correct 1227 ms 73444 KB Output is correct
19 Correct 1233 ms 73368 KB Output is correct
20 Correct 1235 ms 73664 KB Output is correct
21 Correct 1286 ms 73232 KB Output is correct
22 Correct 1243 ms 73908 KB Output is correct
23 Correct 1852 ms 131244 KB Output is correct
24 Correct 1912 ms 127704 KB Output is correct
25 Correct 1826 ms 127488 KB Output is correct
26 Correct 41 ms 4460 KB Output is correct
27 Correct 1130 ms 99512 KB Output is correct
28 Correct 1075 ms 98936 KB Output is correct
29 Correct 1002 ms 53392 KB Output is correct
30 Correct 1034 ms 46476 KB Output is correct
31 Correct 1000 ms 73028 KB Output is correct
32 Correct 815 ms 97744 KB Output is correct
33 Correct 1189 ms 100800 KB Output is correct
34 Correct 980 ms 72332 KB Output is correct
35 Correct 36 ms 4424 KB Output is correct
36 Correct 1102 ms 92228 KB Output is correct
37 Correct 876 ms 64536 KB Output is correct
38 Correct 787 ms 48568 KB Output is correct
39 Correct 640 ms 40388 KB Output is correct
40 Correct 574 ms 28776 KB Output is correct
41 Correct 676 ms 38140 KB Output is correct
42 Correct 574 ms 28172 KB Output is correct
43 Correct 1258 ms 8148 KB Output is correct
44 Correct 34 ms 5820 KB Output is correct
45 Correct 143 ms 8568 KB Output is correct
46 Correct 103 ms 8756 KB Output is correct
47 Correct 743 ms 10428 KB Output is correct
48 Correct 1195 ms 11988 KB Output is correct
49 Correct 756 ms 10472 KB Output is correct
50 Correct 644 ms 9232 KB Output is correct
51 Correct 613 ms 9260 KB Output is correct
52 Correct 642 ms 8952 KB Output is correct
53 Correct 966 ms 10888 KB Output is correct
54 Correct 978 ms 10968 KB Output is correct
55 Correct 991 ms 10692 KB Output is correct
56 Correct 646 ms 10436 KB Output is correct
57 Correct 704 ms 10488 KB Output is correct
58 Correct 1267 ms 12148 KB Output is correct
59 Correct 1301 ms 12112 KB Output is correct
60 Correct 1257 ms 12036 KB Output is correct
61 Correct 1218 ms 11960 KB Output is correct
62 Correct 1101 ms 10920 KB Output is correct
63 Correct 1062 ms 10900 KB Output is correct
64 Correct 1210 ms 11708 KB Output is correct
65 Correct 752 ms 9804 KB Output is correct
66 Correct 1187 ms 73344 KB Output is correct
67 Correct 1572 ms 102728 KB Output is correct
68 Correct 1284 ms 71692 KB Output is correct
69 Correct 850 ms 28912 KB Output is correct
70 Correct 1460 ms 88996 KB Output is correct
71 Correct 1533 ms 91572 KB Output is correct
72 Correct 1523 ms 91832 KB Output is correct
73 Correct 1242 ms 72184 KB Output is correct
74 Correct 1286 ms 72256 KB Output is correct
75 Correct 1261 ms 72556 KB Output is correct
76 Correct 934 ms 35868 KB Output is correct
77 Correct 944 ms 34392 KB Output is correct
78 Correct 910 ms 32988 KB Output is correct
79 Correct 737 ms 19248 KB Output is correct
80 Correct 730 ms 18032 KB Output is correct
81 Correct 686 ms 17644 KB Output is correct
82 Correct 707 ms 17424 KB Output is correct
83 Correct 731 ms 16824 KB Output is correct
84 Correct 718 ms 16200 KB Output is correct
85 Correct 1683 ms 79164 KB Output is correct
86 Correct 173 ms 15328 KB Output is correct
87 Correct 118 ms 19684 KB Output is correct
88 Correct 1166 ms 91032 KB Output is correct
89 Correct 1673 ms 77996 KB Output is correct
90 Correct 1155 ms 99744 KB Output is correct
91 Correct 1306 ms 76432 KB Output is correct
92 Correct 1309 ms 76192 KB Output is correct
93 Correct 1920 ms 113736 KB Output is correct
94 Correct 1489 ms 77832 KB Output is correct
95 Correct 1470 ms 78068 KB Output is correct
96 Correct 1766 ms 118436 KB Output is correct
97 Correct 830 ms 43564 KB Output is correct
98 Correct 962 ms 40700 KB Output is correct
99 Correct 1718 ms 80116 KB Output is correct
100 Correct 1696 ms 78912 KB Output is correct
101 Correct 1754 ms 78976 KB Output is correct
102 Correct 1745 ms 79028 KB Output is correct
103 Correct 1923 ms 123792 KB Output is correct
104 Correct 1906 ms 123432 KB Output is correct
105 Correct 1408 ms 51480 KB Output is correct
106 Correct 1092 ms 31308 KB Output is correct
107 Correct 1255 ms 58036 KB Output is correct
108 Correct 1827 ms 114116 KB Output is correct
109 Correct 1315 ms 117612 KB Output is correct