oj.uz

답안 #684500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684500 2023-01-21T11:06:51 Z noedit 다리 (APIO19_bridges) C++17
100 / 100
 2141 ms 7832 KB 
#include <bits/stdc++.h>
//#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;
//
//#define int long long
////#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

const int MAXN = 5e4 + 5;
const int B = 1400;
const int MAXQ = 1e5 + 5;

int sz[MAXN], p[MAXN];
array<int, 4> rb[MAXQ];
int rb_pt = 0;

int edges[B];
int active[MAXQ];
int edges_pt = 0;
array<int, 4> act[MAXQ + B];
int act_pt = 0;

void init(int n)
{
    rb_pt = 0;
    fill(sz, sz + n, 1);
    iota(p, p + n, 0);
}
int get_par(int a)
{
    if (p[a] == a)
        return a;
    return get_par(p[a]);
}
void mrg(int a, int b)
{
    a = get_par(a);
    b = get_par(b);
    if (a != b)
    {
        if (sz[a] < sz[b])
            swap(a, b);
        rb[rb_pt++] = {b, a, p[b], sz[a]};
        sz[a] += sz[b];
        p[b] = a;
    }
}
void rollback(int x)
{
    while (rb_pt > x)
    {
        auto&[b, a, pb, sza] = rb[rb_pt - 1];
        rb_pt--;
        p[b] = pb;
        sz[a] = sza;
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<array<int, 3> > es(m);
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        es[i] = {w, u, v};
    }
    int q;
    cin >> q;
    vector<array<int, 3> > qs(q);
    for (int i = 0; i < q; i++)
    {
        int t, u, w;
        cin >> t >> u >> w;
        u--;
        qs[i] = {t, u, w};
    }
    vector<int> ans(q, -1);
    int active_flag = 0;
    for (int i = 0; i < q; i += B)
    {
        //vector<bool> active(m);
        active_flag++;
        //vector<int> edges;
        edges_pt = 0;
        auto ess = es;
        //edges.reserve(B);
        //vector<array<int, 4> > act;
        act_pt = 0;
        //act.reserve(B + m);
        for (int j = i; j < min(q, i + B); j++)
        {
            auto& [t, u, w] = qs[j];
            if (t == 1)
            {
                active[u] = active_flag;
                ess[u][0] = w;
                edges[edges_pt++] = j;
            }
            else
            {
                act[act_pt++] = {w, 0, u, j};
            }
        }
        sort(edges, edges + edges_pt, [&](int a, int b)
        {
            return qs[a][1] < qs[b][1] || (qs[a][1] == qs[b][1] && a < b);
        });
        for (int j = 0; j < m; j++)
        {
            auto& [w, u, v] = es[j];
            if (active[j] != active_flag)
            {
                act[act_pt++] = {w, 1, u, v};
            }
        }
        sort(act, act + act_pt, greater<array<int, 4> > ());
        init(n);
        for (int _ = 0; _ < act_pt; _++)
        {
            auto&[w, t, u, v] = act[_];
            if (t == 0)
            {
                int kek = rb_pt;
                for (int k  = 0; k < (int)edges_pt;)
                {
                    int bebra = k;
                    int wei = -1;
                    while (bebra < (int)edges_pt && qs[edges[bebra]][1] == qs[edges[k]][1])
                    {
                        if (edges[bebra] < v)
                        {
                            wei = qs[edges[bebra]][2];
                        }
                        ++bebra;
                    }
                    int numb = qs[edges[k]][1];
                    if (wei == -1)
                    {
                        wei = es[numb][0];
                    }
                    if (w <= wei)
                    {
                        mrg(es[numb][1], es[numb][2]);
                    }
                    k = bebra;

                }
                ans[v] = sz[get_par(u)];
                rollback(kek);
            }
            else
            {
                mrg(u, v);
            }
        }
        es = ess;
    }
    for (auto& i : ans)
    {
        if (i != -1)
            cout << i << '\n';
    }
}
//
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
    return 0;
}
//
//
///*
//4 4
//1 2 1 3
//1 1
//1 2
//1 3
//1 4
//*/

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 50 ms 676 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 25 ms 600 KB Output is correct
6 Correct 18 ms 604 KB Output is correct
7 Correct 27 ms 596 KB Output is correct
8 Correct 21 ms 596 KB Output is correct
9 Correct 21 ms 564 KB Output is correct
10 Correct 21 ms 640 KB Output is correct
11 Correct 20 ms 640 KB Output is correct
12 Correct 23 ms 620 KB Output is correct
13 Correct 30 ms 596 KB Output is correct
14 Correct 28 ms 644 KB Output is correct
15 Correct 27 ms 636 KB Output is correct
16 Correct 22 ms 596 KB Output is correct
17 Correct 23 ms 580 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1286 ms 5480 KB Output is correct
2 Correct 1237 ms 5484 KB Output is correct
3 Correct 1252 ms 5484 KB Output is correct
4 Correct 1232 ms 5504 KB Output is correct
5 Correct 1330 ms 5504 KB Output is correct
6 Correct 2039 ms 5736 KB Output is correct
7 Correct 2070 ms 5744 KB Output is correct
8 Correct 1989 ms 5744 KB Output is correct
9 Correct 37 ms 2504 KB Output is correct
10 Correct 1491 ms 5608 KB Output is correct
11 Correct 1443 ms 5608 KB Output is correct
12 Correct 965 ms 5884 KB Output is correct
13 Correct 957 ms 5464 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1044 ms 4348 KB Output is correct
2 Correct 921 ms 2848 KB Output is correct
3 Correct 1260 ms 4472 KB Output is correct
4 Correct 1018 ms 4472 KB Output is correct
5 Correct 32 ms 2372 KB Output is correct
6 Correct 1172 ms 4480 KB Output is correct
7 Correct 937 ms 4476 KB Output is correct
8 Correct 797 ms 4348 KB Output is correct
9 Correct 580 ms 4584 KB Output is correct
10 Correct 506 ms 4500 KB Output is correct
11 Correct 615 ms 4332 KB Output is correct
12 Correct 543 ms 4332 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 942 ms 7648 KB Output is correct
2 Correct 32 ms 2380 KB Output is correct
3 Correct 120 ms 4700 KB Output is correct
4 Correct 171 ms 4668 KB Output is correct
5 Correct 1239 ms 7632 KB Output is correct
6 Correct 937 ms 7624 KB Output is correct
7 Correct 1229 ms 7628 KB Output is correct
8 Correct 469 ms 5428 KB Output is correct
9 Correct 446 ms 5428 KB Output is correct
10 Correct 457 ms 5624 KB Output is correct
11 Correct 709 ms 6540 KB Output is correct
12 Correct 708 ms 6536 KB Output is correct
13 Correct 701 ms 6756 KB Output is correct
14 Correct 1213 ms 7748 KB Output is correct
15 Correct 1245 ms 7756 KB Output is correct
16 Correct 984 ms 7628 KB Output is correct
17 Correct 959 ms 7620 KB Output is correct
18 Correct 953 ms 7620 KB Output is correct
19 Correct 944 ms 7616 KB Output is correct
20 Correct 812 ms 7120 KB Output is correct
21 Correct 811 ms 7104 KB Output is correct
22 Correct 924 ms 7664 KB Output is correct
23 Correct 986 ms 6884 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1286 ms 5480 KB Output is correct
2 Correct 1237 ms 5484 KB Output is correct
3 Correct 1252 ms 5484 KB Output is correct
4 Correct 1232 ms 5504 KB Output is correct
5 Correct 1330 ms 5504 KB Output is correct
6 Correct 2039 ms 5736 KB Output is correct
7 Correct 2070 ms 5744 KB Output is correct
8 Correct 1989 ms 5744 KB Output is correct
9 Correct 37 ms 2504 KB Output is correct
10 Correct 1491 ms 5608 KB Output is correct
11 Correct 1443 ms 5608 KB Output is correct
12 Correct 965 ms 5884 KB Output is correct
13 Correct 957 ms 5464 KB Output is correct
14 Correct 1044 ms 4348 KB Output is correct
15 Correct 921 ms 2848 KB Output is correct
16 Correct 1260 ms 4472 KB Output is correct
17 Correct 1018 ms 4472 KB Output is correct
18 Correct 32 ms 2372 KB Output is correct
19 Correct 1172 ms 4480 KB Output is correct
20 Correct 937 ms 4476 KB Output is correct
21 Correct 797 ms 4348 KB Output is correct
22 Correct 580 ms 4584 KB Output is correct
23 Correct 506 ms 4500 KB Output is correct
24 Correct 615 ms 4332 KB Output is correct
25 Correct 543 ms 4332 KB Output is correct
26 Correct 1262 ms 5608 KB Output is correct
27 Correct 1691 ms 5608 KB Output is correct
28 Correct 1343 ms 5612 KB Output is correct
29 Correct 874 ms 5612 KB Output is correct
30 Correct 1610 ms 5560 KB Output is correct
31 Correct 1608 ms 5608 KB Output is correct
32 Correct 1647 ms 5608 KB Output is correct
33 Correct 1327 ms 5484 KB Output is correct
34 Correct 1355 ms 5484 KB Output is correct
35 Correct 1343 ms 5476 KB Output is correct
36 Correct 946 ms 5580 KB Output is correct
37 Correct 929 ms 5652 KB Output is correct
38 Correct 917 ms 5484 KB Output is correct
39 Correct 615 ms 5572 KB Output is correct
40 Correct 612 ms 5636 KB Output is correct
41 Correct 611 ms 5580 KB Output is correct
42 Correct 632 ms 5464 KB Output is correct
43 Correct 627 ms 5464 KB Output is correct
44 Correct 627 ms 5468 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 50 ms 676 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 25 ms 600 KB Output is correct
6 Correct 18 ms 604 KB Output is correct
7 Correct 27 ms 596 KB Output is correct
8 Correct 21 ms 596 KB Output is correct
9 Correct 21 ms 564 KB Output is correct
10 Correct 21 ms 640 KB Output is correct
11 Correct 20 ms 640 KB Output is correct
12 Correct 23 ms 620 KB Output is correct
13 Correct 30 ms 596 KB Output is correct
14 Correct 28 ms 644 KB Output is correct
15 Correct 27 ms 636 KB Output is correct
16 Correct 22 ms 596 KB Output is correct
17 Correct 23 ms 580 KB Output is correct
18 Correct 1286 ms 5480 KB Output is correct
19 Correct 1237 ms 5484 KB Output is correct
20 Correct 1252 ms 5484 KB Output is correct
21 Correct 1232 ms 5504 KB Output is correct
22 Correct 1330 ms 5504 KB Output is correct
23 Correct 2039 ms 5736 KB Output is correct
24 Correct 2070 ms 5744 KB Output is correct
25 Correct 1989 ms 5744 KB Output is correct
26 Correct 37 ms 2504 KB Output is correct
27 Correct 1491 ms 5608 KB Output is correct
28 Correct 1443 ms 5608 KB Output is correct
29 Correct 965 ms 5884 KB Output is correct
30 Correct 957 ms 5464 KB Output is correct
31 Correct 1044 ms 4348 KB Output is correct
32 Correct 921 ms 2848 KB Output is correct
33 Correct 1260 ms 4472 KB Output is correct
34 Correct 1018 ms 4472 KB Output is correct
35 Correct 32 ms 2372 KB Output is correct
36 Correct 1172 ms 4480 KB Output is correct
37 Correct 937 ms 4476 KB Output is correct
38 Correct 797 ms 4348 KB Output is correct
39 Correct 580 ms 4584 KB Output is correct
40 Correct 506 ms 4500 KB Output is correct
41 Correct 615 ms 4332 KB Output is correct
42 Correct 543 ms 4332 KB Output is correct
43 Correct 942 ms 7648 KB Output is correct
44 Correct 32 ms 2380 KB Output is correct
45 Correct 120 ms 4700 KB Output is correct
46 Correct 171 ms 4668 KB Output is correct
47 Correct 1239 ms 7632 KB Output is correct
48 Correct 937 ms 7624 KB Output is correct
49 Correct 1229 ms 7628 KB Output is correct
50 Correct 469 ms 5428 KB Output is correct
51 Correct 446 ms 5428 KB Output is correct
52 Correct 457 ms 5624 KB Output is correct
53 Correct 709 ms 6540 KB Output is correct
54 Correct 708 ms 6536 KB Output is correct
55 Correct 701 ms 6756 KB Output is correct
56 Correct 1213 ms 7748 KB Output is correct
57 Correct 1245 ms 7756 KB Output is correct
58 Correct 984 ms 7628 KB Output is correct
59 Correct 959 ms 7620 KB Output is correct
60 Correct 953 ms 7620 KB Output is correct
61 Correct 944 ms 7616 KB Output is correct
62 Correct 812 ms 7120 KB Output is correct
63 Correct 811 ms 7104 KB Output is correct
64 Correct 924 ms 7664 KB Output is correct
65 Correct 986 ms 6884 KB Output is correct
66 Correct 1262 ms 5608 KB Output is correct
67 Correct 1691 ms 5608 KB Output is correct
68 Correct 1343 ms 5612 KB Output is correct
69 Correct 874 ms 5612 KB Output is correct
70 Correct 1610 ms 5560 KB Output is correct
71 Correct 1608 ms 5608 KB Output is correct
72 Correct 1647 ms 5608 KB Output is correct
73 Correct 1327 ms 5484 KB Output is correct
74 Correct 1355 ms 5484 KB Output is correct
75 Correct 1343 ms 5476 KB Output is correct
76 Correct 946 ms 5580 KB Output is correct
77 Correct 929 ms 5652 KB Output is correct
78 Correct 917 ms 5484 KB Output is correct
79 Correct 615 ms 5572 KB Output is correct
80 Correct 612 ms 5636 KB Output is correct
81 Correct 611 ms 5580 KB Output is correct
82 Correct 632 ms 5464 KB Output is correct
83 Correct 627 ms 5464 KB Output is correct
84 Correct 627 ms 5468 KB Output is correct
85 Correct 1706 ms 7748 KB Output is correct
86 Correct 177 ms 5056 KB Output is correct
87 Correct 183 ms 5060 KB Output is correct
88 Correct 1987 ms 7748 KB Output is correct
89 Correct 1661 ms 7748 KB Output is correct
90 Correct 1988 ms 7684 KB Output is correct
91 Correct 1418 ms 5508 KB Output is correct
92 Correct 1366 ms 5612 KB Output is correct
93 Correct 2141 ms 5620 KB Output is correct
94 Correct 1539 ms 6680 KB Output is correct
95 Correct 1543 ms 6568 KB Output is correct
96 Correct 1893 ms 6592 KB Output is correct
97 Correct 1397 ms 7832 KB Output is correct
98 Correct 1548 ms 7408 KB Output is correct
99 Correct 1743 ms 7672 KB Output is correct
100 Correct 1738 ms 7716 KB Output is correct
101 Correct 1763 ms 7752 KB Output is correct
102 Correct 1743 ms 7732 KB Output is correct
103 Correct 2071 ms 7052 KB Output is correct
104 Correct 2051 ms 7048 KB Output is correct
105 Correct 1287 ms 6800 KB Output is correct
106 Correct 981 ms 6448 KB Output is correct
107 Correct 1114 ms 7192 KB Output is correct
108 Correct 1888 ms 7476 KB Output is correct
109 Correct 2004 ms 6780 KB Output is correct