oj.uz

Submission #555378

# Submission time Handle Problem Language Result Execution time Memory
555378 2022-04-30T18:04:51 Z Alexandruabcde Bridges (APIO19_bridges) C++14
100 / 100
 2355 ms 77456 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> PII;
constexpr int NMAX = 5e4 + 5;
constexpr int MMAX = 1e5 + 5;

struct Edge {
    int x, y;
    int weight;
};
Edge E[MMAX];

struct Query {
    int tip;
    int who, weight;
};
Query q[MMAX];

bool cmp_Edge (int a, int b) {
    return E[a].weight > E[b].weight;
}

bool cmp_Query (int a, int b) {
    return q[a].weight > q[b].weight;
}

int ans[MMAX];

int N, M, Q;

int Dad[NMAX];
int Size[NMAX];

void Reset () {
    for (int i = 1; i <= N; ++ i ) {
        Dad[i] = i;
        Size[i] = 1;
    }
}

int Reprezentant (int x) {
    if (Dad[x] == x) return x;

    return Reprezentant(Dad[x]);
}

vector <PII> S;

void Union (int x, int y) {
    x = Reprezentant(x);
    y = Reprezentant(y);

    if (x == y) return;

    if (Size[x] > Size[y]) swap(x, y);

    Dad[x] = y;
    Size[y] += Size[x];
    S.push_back({x, y});
}

void Return (int sz) {
    while (S.size() > sz) {
        int x = S.back().first;
        int y = S.back().second;

        Dad[x] = x;
        Size[y] -= Size[x];
        S.pop_back();
    }
}

bool changed[MMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= M; ++ i )
        cin >> E[i].x >> E[i].y >> E[i].weight;

    cin >> Q;
    for (int i = 1; i <= Q; ++ i )
        cin >> q[i].tip >> q[i].who >> q[i].weight;
}

vector <int> ForcedUnion[1005];

void Solve () {
    int Batch = 1000;

    for (int st = 1; st <= Q; st += Batch) {
        Reset();
        int dr = min(st + Batch - 1, Q);

        vector <int> modif;
        vector <int> ask;
        vector <int> nemodif;

        for (int i = st; i <= dr; ++ i ) {
            if (q[i].tip == 1) {
                changed[q[i].who] = 1;
                modif.push_back(i);
            }
            else ask.push_back(i);
        }

        for (int i = 1; i <= M; ++ i )
            if (!changed[i]) nemodif.push_back(i);

        for (int i = st; i <= dr; ++ i ) {
            if (q[i].tip == 1) E[q[i].who].weight = q[i].weight;
            else {
                ForcedUnion[i-st+1].clear();

                for (auto chg : modif)
                    if (E[q[chg].who].weight >= q[i].weight) ForcedUnion[i-st+1].push_back(q[chg].who);
            }
        }

        sort(nemodif.begin(), nemodif.end(), cmp_Edge);
        sort(ask.begin(), ask.end(), cmp_Query);

        int ind = 0;
        for (auto itr : ask) {
            while (ind < nemodif.size() && E[nemodif[ind]].weight >= q[itr].weight) {
                Union(E[nemodif[ind]].x, E[nemodif[ind]].y);

                ++ ind;
            }

            int GoBack = S.size();

            for (auto index : ForcedUnion[itr - st + 1])
                Union(E[index].x, E[index].y);

            ans[itr] = Size[Reprezentant(q[itr].who)];

            Return(GoBack);
        }

        for (int i = st; i <= dr; ++ i )
            if (q[i].tip == 1)
                changed[q[i].who] = 0;
    }

    for (int i = 1; i <= Q; ++ i )
        if (q[i].tip == 2) cout << ans[i] << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Compilation message

bridges.cpp: In function 'void Return(int)':
bridges.cpp:65:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |     while (S.size() > sz) {
      |            ~~~~~~~~~^~~~
bridges.cpp: In function 'void Solve()':
bridges.cpp:130:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             while (ind < nemodif.size() && E[nemodif[ind]].weight >= q[itr].weight) {
      |                    ~~~~^~~~~~~~~~~~~~~~

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 35 ms 2644 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 35 ms 2772 KB Output is correct
6 Correct 26 ms 2572 KB Output is correct
7 Correct 31 ms 3384 KB Output is correct
8 Correct 39 ms 2636 KB Output is correct
9 Correct 40 ms 4300 KB Output is correct
10 Correct 36 ms 2752 KB Output is correct
11 Correct 36 ms 2560 KB Output is correct
12 Correct 43 ms 2764 KB Output is correct
13 Correct 42 ms 2656 KB Output is correct
14 Correct 40 ms 2620 KB Output is correct
15 Correct 42 ms 2644 KB Output is correct
16 Correct 38 ms 3940 KB Output is correct
17 Correct 38 ms 3340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1384 ms 71828 KB Output is correct
2 Correct 1391 ms 71700 KB Output is correct
3 Correct 1379 ms 71960 KB Output is correct
4 Correct 1407 ms 71616 KB Output is correct
5 Correct 1502 ms 71820 KB Output is correct
6 Correct 1998 ms 73328 KB Output is correct
7 Correct 1934 ms 73196 KB Output is correct
8 Correct 1933 ms 73332 KB Output is correct
9 Correct 33 ms 2124 KB Output is correct
10 Correct 1052 ms 73392 KB Output is correct
11 Correct 1000 ms 73432 KB Output is correct
12 Correct 1253 ms 69648 KB Output is correct
13 Correct 1236 ms 73352 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 38244 KB Output is correct
2 Correct 695 ms 14464 KB Output is correct
3 Correct 1231 ms 40056 KB Output is correct
4 Correct 1055 ms 38324 KB Output is correct
5 Correct 35 ms 2124 KB Output is correct
6 Correct 1145 ms 38328 KB Output is correct
7 Correct 961 ms 37944 KB Output is correct
8 Correct 866 ms 37964 KB Output is correct
9 Correct 721 ms 36204 KB Output is correct
10 Correct 677 ms 36296 KB Output is correct
11 Correct 776 ms 39824 KB Output is correct
12 Correct 699 ms 39568 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1787 ms 70404 KB Output is correct
2 Correct 34 ms 3468 KB Output is correct
3 Correct 189 ms 4460 KB Output is correct
4 Correct 88 ms 4576 KB Output is correct
5 Correct 929 ms 72420 KB Output is correct
6 Correct 1768 ms 74020 KB Output is correct
7 Correct 934 ms 72168 KB Output is correct
8 Correct 886 ms 71600 KB Output is correct
9 Correct 883 ms 71640 KB Output is correct
10 Correct 900 ms 71588 KB Output is correct
11 Correct 1347 ms 72996 KB Output is correct
12 Correct 1368 ms 73084 KB Output is correct
13 Correct 1367 ms 72724 KB Output is correct
14 Correct 866 ms 72372 KB Output is correct
15 Correct 903 ms 72236 KB Output is correct
16 Correct 1794 ms 73704 KB Output is correct
17 Correct 1800 ms 73644 KB Output is correct
18 Correct 1795 ms 73940 KB Output is correct
19 Correct 1806 ms 73844 KB Output is correct
20 Correct 1523 ms 73036 KB Output is correct
21 Correct 1538 ms 72956 KB Output is correct
22 Correct 1739 ms 73448 KB Output is correct
23 Correct 1020 ms 71784 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1384 ms 71828 KB Output is correct
2 Correct 1391 ms 71700 KB Output is correct
3 Correct 1379 ms 71960 KB Output is correct
4 Correct 1407 ms 71616 KB Output is correct
5 Correct 1502 ms 71820 KB Output is correct
6 Correct 1998 ms 73328 KB Output is correct
7 Correct 1934 ms 73196 KB Output is correct
8 Correct 1933 ms 73332 KB Output is correct
9 Correct 33 ms 2124 KB Output is correct
10 Correct 1052 ms 73392 KB Output is correct
11 Correct 1000 ms 73432 KB Output is correct
12 Correct 1253 ms 69648 KB Output is correct
13 Correct 1236 ms 73352 KB Output is correct
14 Correct 1077 ms 38244 KB Output is correct
15 Correct 695 ms 14464 KB Output is correct
16 Correct 1231 ms 40056 KB Output is correct
17 Correct 1055 ms 38324 KB Output is correct
18 Correct 35 ms 2124 KB Output is correct
19 Correct 1145 ms 38328 KB Output is correct
20 Correct 961 ms 37944 KB Output is correct
21 Correct 866 ms 37964 KB Output is correct
22 Correct 721 ms 36204 KB Output is correct
23 Correct 677 ms 36296 KB Output is correct
24 Correct 776 ms 39824 KB Output is correct
25 Correct 699 ms 39568 KB Output is correct
26 Correct 1476 ms 71716 KB Output is correct
27 Correct 1671 ms 73412 KB Output is correct
28 Correct 1445 ms 71596 KB Output is correct
29 Correct 1131 ms 71484 KB Output is correct
30 Correct 1628 ms 73308 KB Output is correct
31 Correct 1671 ms 73484 KB Output is correct
32 Correct 1653 ms 73500 KB Output is correct
33 Correct 1457 ms 71612 KB Output is correct
34 Correct 1502 ms 71648 KB Output is correct
35 Correct 1459 ms 71704 KB Output is correct
36 Correct 1181 ms 71428 KB Output is correct
37 Correct 1149 ms 71348 KB Output is correct
38 Correct 1133 ms 71332 KB Output is correct
39 Correct 1004 ms 69648 KB Output is correct
40 Correct 1075 ms 69668 KB Output is correct
41 Correct 986 ms 69524 KB Output is correct
42 Correct 979 ms 72752 KB Output is correct
43 Correct 965 ms 72536 KB Output is correct
44 Correct 974 ms 72520 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 35 ms 2644 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 35 ms 2772 KB Output is correct
6 Correct 26 ms 2572 KB Output is correct
7 Correct 31 ms 3384 KB Output is correct
8 Correct 39 ms 2636 KB Output is correct
9 Correct 40 ms 4300 KB Output is correct
10 Correct 36 ms 2752 KB Output is correct
11 Correct 36 ms 2560 KB Output is correct
12 Correct 43 ms 2764 KB Output is correct
13 Correct 42 ms 2656 KB Output is correct
14 Correct 40 ms 2620 KB Output is correct
15 Correct 42 ms 2644 KB Output is correct
16 Correct 38 ms 3940 KB Output is correct
17 Correct 38 ms 3340 KB Output is correct
18 Correct 1384 ms 71828 KB Output is correct
19 Correct 1391 ms 71700 KB Output is correct
20 Correct 1379 ms 71960 KB Output is correct
21 Correct 1407 ms 71616 KB Output is correct
22 Correct 1502 ms 71820 KB Output is correct
23 Correct 1998 ms 73328 KB Output is correct
24 Correct 1934 ms 73196 KB Output is correct
25 Correct 1933 ms 73332 KB Output is correct
26 Correct 33 ms 2124 KB Output is correct
27 Correct 1052 ms 73392 KB Output is correct
28 Correct 1000 ms 73432 KB Output is correct
29 Correct 1253 ms 69648 KB Output is correct
30 Correct 1236 ms 73352 KB Output is correct
31 Correct 1077 ms 38244 KB Output is correct
32 Correct 695 ms 14464 KB Output is correct
33 Correct 1231 ms 40056 KB Output is correct
34 Correct 1055 ms 38324 KB Output is correct
35 Correct 35 ms 2124 KB Output is correct
36 Correct 1145 ms 38328 KB Output is correct
37 Correct 961 ms 37944 KB Output is correct
38 Correct 866 ms 37964 KB Output is correct
39 Correct 721 ms 36204 KB Output is correct
40 Correct 677 ms 36296 KB Output is correct
41 Correct 776 ms 39824 KB Output is correct
42 Correct 699 ms 39568 KB Output is correct
43 Correct 1787 ms 70404 KB Output is correct
44 Correct 34 ms 3468 KB Output is correct
45 Correct 189 ms 4460 KB Output is correct
46 Correct 88 ms 4576 KB Output is correct
47 Correct 929 ms 72420 KB Output is correct
48 Correct 1768 ms 74020 KB Output is correct
49 Correct 934 ms 72168 KB Output is correct
50 Correct 886 ms 71600 KB Output is correct
51 Correct 883 ms 71640 KB Output is correct
52 Correct 900 ms 71588 KB Output is correct
53 Correct 1347 ms 72996 KB Output is correct
54 Correct 1368 ms 73084 KB Output is correct
55 Correct 1367 ms 72724 KB Output is correct
56 Correct 866 ms 72372 KB Output is correct
57 Correct 903 ms 72236 KB Output is correct
58 Correct 1794 ms 73704 KB Output is correct
59 Correct 1800 ms 73644 KB Output is correct
60 Correct 1795 ms 73940 KB Output is correct
61 Correct 1806 ms 73844 KB Output is correct
62 Correct 1523 ms 73036 KB Output is correct
63 Correct 1538 ms 72956 KB Output is correct
64 Correct 1739 ms 73448 KB Output is correct
65 Correct 1020 ms 71784 KB Output is correct
66 Correct 1476 ms 71716 KB Output is correct
67 Correct 1671 ms 73412 KB Output is correct
68 Correct 1445 ms 71596 KB Output is correct
69 Correct 1131 ms 71484 KB Output is correct
70 Correct 1628 ms 73308 KB Output is correct
71 Correct 1671 ms 73484 KB Output is correct
72 Correct 1653 ms 73500 KB Output is correct
73 Correct 1457 ms 71612 KB Output is correct
74 Correct 1502 ms 71648 KB Output is correct
75 Correct 1459 ms 71704 KB Output is correct
76 Correct 1181 ms 71428 KB Output is correct
77 Correct 1149 ms 71348 KB Output is correct
78 Correct 1133 ms 71332 KB Output is correct
79 Correct 1004 ms 69648 KB Output is correct
80 Correct 1075 ms 69668 KB Output is correct
81 Correct 986 ms 69524 KB Output is correct
82 Correct 979 ms 72752 KB Output is correct
83 Correct 965 ms 72536 KB Output is correct
84 Correct 974 ms 72520 KB Output is correct
85 Correct 2214 ms 76540 KB Output is correct
86 Correct 223 ms 6620 KB Output is correct
87 Correct 128 ms 8124 KB Output is correct
88 Correct 1360 ms 76696 KB Output is correct
89 Correct 2201 ms 76572 KB Output is correct
90 Correct 1327 ms 76636 KB Output is correct
91 Correct 1505 ms 74476 KB Output is correct
92 Correct 1458 ms 74336 KB Output is correct
93 Correct 1974 ms 75676 KB Output is correct
94 Correct 1828 ms 75664 KB Output is correct
95 Correct 1846 ms 75672 KB Output is correct
96 Correct 2115 ms 77020 KB Output is correct
97 Correct 1064 ms 72896 KB Output is correct
98 Correct 1133 ms 76676 KB Output is correct
99 Correct 2279 ms 76668 KB Output is correct
100 Correct 2234 ms 76352 KB Output is correct
101 Correct 2294 ms 76548 KB Output is correct
102 Correct 2294 ms 76580 KB Output is correct
103 Correct 2355 ms 77456 KB Output is correct
104 Correct 2352 ms 77404 KB Output is correct
105 Correct 1815 ms 77296 KB Output is correct
106 Correct 1506 ms 76844 KB Output is correct
107 Correct 1695 ms 73688 KB Output is correct
108 Correct 2247 ms 76692 KB Output is correct
109 Correct 1554 ms 76400 KB Output is correct