oj.uz

Submission #255976

# Submission time Handle Problem Language Result Execution time Memory
255976 2020-08-02T07:24:57 Z AM1648 Bridges (APIO19_bridges) C++17
100 / 100
 2873 ms 81784 KB 
/* be name khoda */

// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

// -----------------------------------------------------------------------

const ll maxn = 50010;
const ll maxm = 100010;
const ll SQ = 400;

ll n, m, qn, qm, cm;
pip es[maxm];
ppi qs[maxm], cs[maxm];
ll g[maxn][SQ], deg[maxn];
ll rt[maxn], sz[maxn], qt[maxm], es_sort[maxm], lst[maxm];
ll vis[maxn];
bool chg[maxm];
ll res[maxm];

ll root(ll x) {
    return rt[x] == x ? x : rt[x] = root(rt[x]);
}

ll dfs(ll x) {
    ll s = 0;
    fori (yi, deg[x]) if (vis[g[x][yi]] != vis[x]) vis[g[x][yi]] = vis[x], s += dfs(g[x][yi]);
    return s + sz[x];
}

ll search(ll s, ll w, ll t) {
    forir (i, cm) if (cs[i].S < t && lst[cs[i].F.F] != t + 1) {
        if (cs[i].F.S >= w) {
            auto [a, b] = es[cs[i].F.F].S;
            a = root(a), b = root(b);
            if (a != b) g[a][deg[a]++] = b, g[b][deg[b]++] = a;
        }
        lst[cs[i].F.F] = t + 1;
    }
    fori (i, cm) if (lst[cs[i].F.F] != t + 1 && es[cs[i].F.F].F >= w) {
        auto [a, b] = es[cs[i].F.F].S;
        a = root(a), b = root(b);
        if (a != b) g[a][deg[a]++] = b, g[b][deg[b]++] = a;
    }
    vis[root(s)] = t + 1;
    ll r = dfs(rt[s]);
    fori (i, cm) {
        auto [a, b] = es[cs[i].F.F].S;
        a = root(a), b = root(b);
        deg[rt[a]] = deg[rt[b]] = 0;
    }
    return r;
}

void calc() {
    sort(es_sort, es_sort + m, [](const ll a, const ll b) { return es[a].F > es[b].F; });
    sort(qs, qs + qm, greater<ppi>());
    iota(rt, rt + n, 0);
    fill(sz, sz + n, 1);
    fori (i, cm) chg[cs[i].F.F] = 1;
    ll ptr = 0;
    fori (i, m) {
        if (chg[es_sort[i]]) continue;
        while (ptr < qm && qs[ptr].F.F > es[es_sort[i]].F) {
            res[qs[ptr].S] = search(qs[ptr].F.S, qs[ptr].F.F, qs[ptr].S);
            ++ptr;
        }
        auto [a, b] = es[es_sort[i]].S;
        if (root(a) != root(b)) {
            if (sz[rt[a]] > sz[rt[b]]) swap(a, b);
            sz[rt[b]] += sz[rt[a]];
            rt[rt[a]] = rt[b];
        }
    }
    while (ptr < qm) {
        res[qs[ptr].S] = search(qs[ptr].F.S, qs[ptr].F.F, qs[ptr].S);
        ++ptr;
    }
    fori (i, cm) {
        chg[cs[i].F.F] = 0;
        es[cs[i].F.F].F = cs[i].F.S;
    }
    qm = cm = 0;
}

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

    cin >> n >> m;
    fori (i, m) {
        ll a, b, w; cin >> a >> b >> w; --a, --b;
        es[i] = {w, {a, b}};
    }
    iota(es_sort, es_sort + m, 0);
    cin >> qn;
    fori (i, qn) {
        ll t, a, b; cin >> t >> a >> b; --a;
        qt[i] = t;
        if (t == 1) {
            cs[cm++] = {{a, b}, i};
        } else {
            qs[qm++] = {{b, a}, i};
        }
        if ((cm + 1) % SQ == 0) calc();
    }
    calc();
    fori (i, qn) if (qt[i] == 2) cout << res[i] << '\n';

}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 52 ms 768 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 44 ms 632 KB Output is correct
6 Correct 44 ms 632 KB Output is correct
7 Correct 50 ms 760 KB Output is correct
8 Correct 44 ms 764 KB Output is correct
9 Correct 52 ms 760 KB Output is correct
10 Correct 43 ms 760 KB Output is correct
11 Correct 42 ms 760 KB Output is correct
12 Correct 44 ms 760 KB Output is correct
13 Correct 51 ms 888 KB Output is correct
14 Correct 48 ms 768 KB Output is correct
15 Correct 50 ms 760 KB Output is correct
16 Correct 47 ms 760 KB Output is correct
17 Correct 46 ms 760 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1753 ms 80428 KB Output is correct
2 Correct 1779 ms 80308 KB Output is correct
3 Correct 1722 ms 80548 KB Output is correct
4 Correct 1733 ms 80188 KB Output is correct
5 Correct 1705 ms 80284 KB Output is correct
6 Correct 2347 ms 39272 KB Output is correct
7 Correct 2184 ms 39420 KB Output is correct
8 Correct 2131 ms 40312 KB Output is correct
9 Correct 47 ms 2680 KB Output is correct
10 Correct 1814 ms 78636 KB Output is correct
11 Correct 1681 ms 79796 KB Output is correct
12 Correct 2873 ms 17656 KB Output is correct
13 Correct 1443 ms 52804 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 53796 KB Output is correct
2 Correct 1173 ms 14584 KB Output is correct
3 Correct 1690 ms 54008 KB Output is correct
4 Correct 1457 ms 53880 KB Output is correct
5 Correct 45 ms 2680 KB Output is correct
6 Correct 1515 ms 52504 KB Output is correct
7 Correct 1351 ms 53624 KB Output is correct
8 Correct 1251 ms 53752 KB Output is correct
9 Correct 2074 ms 38900 KB Output is correct
10 Correct 1739 ms 41208 KB Output is correct
11 Correct 957 ms 53240 KB Output is correct
12 Correct 931 ms 53752 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 5112 KB Output is correct
2 Correct 42 ms 2680 KB Output is correct
3 Correct 46 ms 2296 KB Output is correct
4 Correct 39 ms 2296 KB Output is correct
5 Correct 79 ms 5112 KB Output is correct
6 Correct 101 ms 5112 KB Output is correct
7 Correct 81 ms 5112 KB Output is correct
8 Correct 75 ms 4088 KB Output is correct
9 Correct 74 ms 4088 KB Output is correct
10 Correct 78 ms 4244 KB Output is correct
11 Correct 98 ms 4428 KB Output is correct
12 Correct 87 ms 4472 KB Output is correct
13 Correct 87 ms 4728 KB Output is correct
14 Correct 79 ms 5240 KB Output is correct
15 Correct 82 ms 5112 KB Output is correct
16 Correct 105 ms 5240 KB Output is correct
17 Correct 111 ms 5368 KB Output is correct
18 Correct 120 ms 5496 KB Output is correct
19 Correct 112 ms 5496 KB Output is correct
20 Correct 108 ms 5408 KB Output is correct
21 Correct 96 ms 5368 KB Output is correct
22 Correct 99 ms 5752 KB Output is correct
23 Correct 73 ms 5368 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1753 ms 80428 KB Output is correct
2 Correct 1779 ms 80308 KB Output is correct
3 Correct 1722 ms 80548 KB Output is correct
4 Correct 1733 ms 80188 KB Output is correct
5 Correct 1705 ms 80284 KB Output is correct
6 Correct 2347 ms 39272 KB Output is correct
7 Correct 2184 ms 39420 KB Output is correct
8 Correct 2131 ms 40312 KB Output is correct
9 Correct 47 ms 2680 KB Output is correct
10 Correct 1814 ms 78636 KB Output is correct
11 Correct 1681 ms 79796 KB Output is correct
12 Correct 2873 ms 17656 KB Output is correct
13 Correct 1443 ms 52804 KB Output is correct
14 Correct 1449 ms 53796 KB Output is correct
15 Correct 1173 ms 14584 KB Output is correct
16 Correct 1690 ms 54008 KB Output is correct
17 Correct 1457 ms 53880 KB Output is correct
18 Correct 45 ms 2680 KB Output is correct
19 Correct 1515 ms 52504 KB Output is correct
20 Correct 1351 ms 53624 KB Output is correct
21 Correct 1251 ms 53752 KB Output is correct
22 Correct 2074 ms 38900 KB Output is correct
23 Correct 1739 ms 41208 KB Output is correct
24 Correct 957 ms 53240 KB Output is correct
25 Correct 931 ms 53752 KB Output is correct
26 Correct 1832 ms 80568 KB Output is correct
27 Correct 2063 ms 79804 KB Output is correct
28 Correct 1838 ms 79848 KB Output is correct
29 Correct 1476 ms 79752 KB Output is correct
30 Correct 2093 ms 80496 KB Output is correct
31 Correct 2298 ms 80356 KB Output is correct
32 Correct 2099 ms 80384 KB Output is correct
33 Correct 1830 ms 80640 KB Output is correct
34 Correct 1828 ms 80416 KB Output is correct
35 Correct 1824 ms 80368 KB Output is correct
36 Correct 1547 ms 80204 KB Output is correct
37 Correct 1531 ms 80376 KB Output is correct
38 Correct 1527 ms 80120 KB Output is correct
39 Correct 1627 ms 58200 KB Output is correct
40 Correct 1580 ms 56988 KB Output is correct
41 Correct 1543 ms 56056 KB Output is correct
42 Correct 1394 ms 81784 KB Output is correct
43 Correct 1399 ms 81760 KB Output is correct
44 Correct 1421 ms 81732 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 52 ms 768 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 44 ms 632 KB Output is correct
6 Correct 44 ms 632 KB Output is correct
7 Correct 50 ms 760 KB Output is correct
8 Correct 44 ms 764 KB Output is correct
9 Correct 52 ms 760 KB Output is correct
10 Correct 43 ms 760 KB Output is correct
11 Correct 42 ms 760 KB Output is correct
12 Correct 44 ms 760 KB Output is correct
13 Correct 51 ms 888 KB Output is correct
14 Correct 48 ms 768 KB Output is correct
15 Correct 50 ms 760 KB Output is correct
16 Correct 47 ms 760 KB Output is correct
17 Correct 46 ms 760 KB Output is correct
18 Correct 1753 ms 80428 KB Output is correct
19 Correct 1779 ms 80308 KB Output is correct
20 Correct 1722 ms 80548 KB Output is correct
21 Correct 1733 ms 80188 KB Output is correct
22 Correct 1705 ms 80284 KB Output is correct
23 Correct 2347 ms 39272 KB Output is correct
24 Correct 2184 ms 39420 KB Output is correct
25 Correct 2131 ms 40312 KB Output is correct
26 Correct 47 ms 2680 KB Output is correct
27 Correct 1814 ms 78636 KB Output is correct
28 Correct 1681 ms 79796 KB Output is correct
29 Correct 2873 ms 17656 KB Output is correct
30 Correct 1443 ms 52804 KB Output is correct
31 Correct 1449 ms 53796 KB Output is correct
32 Correct 1173 ms 14584 KB Output is correct
33 Correct 1690 ms 54008 KB Output is correct
34 Correct 1457 ms 53880 KB Output is correct
35 Correct 45 ms 2680 KB Output is correct
36 Correct 1515 ms 52504 KB Output is correct
37 Correct 1351 ms 53624 KB Output is correct
38 Correct 1251 ms 53752 KB Output is correct
39 Correct 2074 ms 38900 KB Output is correct
40 Correct 1739 ms 41208 KB Output is correct
41 Correct 957 ms 53240 KB Output is correct
42 Correct 931 ms 53752 KB Output is correct
43 Correct 112 ms 5112 KB Output is correct
44 Correct 42 ms 2680 KB Output is correct
45 Correct 46 ms 2296 KB Output is correct
46 Correct 39 ms 2296 KB Output is correct
47 Correct 79 ms 5112 KB Output is correct
48 Correct 101 ms 5112 KB Output is correct
49 Correct 81 ms 5112 KB Output is correct
50 Correct 75 ms 4088 KB Output is correct
51 Correct 74 ms 4088 KB Output is correct
52 Correct 78 ms 4244 KB Output is correct
53 Correct 98 ms 4428 KB Output is correct
54 Correct 87 ms 4472 KB Output is correct
55 Correct 87 ms 4728 KB Output is correct
56 Correct 79 ms 5240 KB Output is correct
57 Correct 82 ms 5112 KB Output is correct
58 Correct 105 ms 5240 KB Output is correct
59 Correct 111 ms 5368 KB Output is correct
60 Correct 120 ms 5496 KB Output is correct
61 Correct 112 ms 5496 KB Output is correct
62 Correct 108 ms 5408 KB Output is correct
63 Correct 96 ms 5368 KB Output is correct
64 Correct 99 ms 5752 KB Output is correct
65 Correct 73 ms 5368 KB Output is correct
66 Correct 1832 ms 80568 KB Output is correct
67 Correct 2063 ms 79804 KB Output is correct
68 Correct 1838 ms 79848 KB Output is correct
69 Correct 1476 ms 79752 KB Output is correct
70 Correct 2093 ms 80496 KB Output is correct
71 Correct 2298 ms 80356 KB Output is correct
72 Correct 2099 ms 80384 KB Output is correct
73 Correct 1830 ms 80640 KB Output is correct
74 Correct 1828 ms 80416 KB Output is correct
75 Correct 1824 ms 80368 KB Output is correct
76 Correct 1547 ms 80204 KB Output is correct
77 Correct 1531 ms 80376 KB Output is correct
78 Correct 1527 ms 80120 KB Output is correct
79 Correct 1627 ms 58200 KB Output is correct
80 Correct 1580 ms 56988 KB Output is correct
81 Correct 1543 ms 56056 KB Output is correct
82 Correct 1394 ms 81784 KB Output is correct
83 Correct 1399 ms 81760 KB Output is correct
84 Correct 1421 ms 81732 KB Output is correct
85 Correct 2419 ms 76016 KB Output is correct
86 Correct 211 ms 3360 KB Output is correct
87 Correct 147 ms 3192 KB Output is correct
88 Correct 1668 ms 69012 KB Output is correct
89 Correct 2358 ms 76664 KB Output is correct
90 Correct 1780 ms 59064 KB Output is correct
91 Correct 1856 ms 81004 KB Output is correct
92 Correct 1829 ms 81180 KB Output is correct
93 Correct 2121 ms 56780 KB Output is correct
94 Correct 2029 ms 79944 KB Output is correct
95 Correct 2199 ms 79812 KB Output is correct
96 Correct 2028 ms 16428 KB Output is correct
97 Correct 1764 ms 26012 KB Output is correct
98 Correct 1640 ms 65612 KB Output is correct
99 Correct 2415 ms 77448 KB Output is correct
100 Correct 2458 ms 77864 KB Output is correct
101 Correct 2469 ms 78964 KB Output is correct
102 Correct 2448 ms 78300 KB Output is correct
103 Correct 2179 ms 7168 KB Output is correct
104 Correct 2165 ms 7264 KB Output is correct
105 Correct 2301 ms 7704 KB Output is correct
106 Correct 2103 ms 10336 KB Output is correct
107 Correct 1887 ms 5856 KB Output is correct
108 Correct 2223 ms 25088 KB Output is correct
109 Correct 1614 ms 8936 KB Output is correct