Submission #872151

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
872151	2023-11-12T11:37:47 Z	Kihihihi	Bridges (APIO19_bridges)	C++17	100 / 100	2613 ms	12688 KB

bridges

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <ctime>
#include <chrono>
#include <random>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <deque>
#include <bitset>
using namespace std;
mt19937_64 rnd(time(NULL));

const int SQ = 1000;

struct edge
{
    int a, b, w;
};

struct query
{
    int qt, x, y;
};

struct dsu
{
    int n;
    vector<int> p, rk, sz;
    vector<vector<pair<int*, int>>> hist;

    dsu(int in)
    {
        n = in;
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        rk.resize(n);
        sz.resize(n, 1);
    }

    int rt(int v)
    {
        return (p[v] == v ? v : rt(p[v]));
    }

    void unite(int a, int b)
    {
        a = rt(a); b = rt(b);
        hist.push_back({});
        if (a == b)
        {
            return;
        }

        hist.back().reserve(4);
        if (rk[a] < rk[b])
        {
            swap(a, b);
        }
        hist.back().push_back({ &p[b], p[b] });
        p[b] = a;
        hist.back().push_back({ &sz[a], sz[a] });
        sz[a] += sz[b];
        hist.back().push_back({ &sz[b], sz[b] });
        sz[b] = 0;
        hist.back().push_back({ &rk[a], rk[a] });
        rk[a] += (rk[a] == rk[b]);
    }

    void ctrlz()
    {
        while (hist.back().size())
        {
            *hist.back().back().first = hist.back().back().second;
            hist.back().pop_back();
        }
        hist.pop_back();
    }

    int get(int v)
    {
        return sz[rt(v)];
    }
};

void solve()
{
    int n, m;
    vector<edge> e;
    cin >> n >> m;
    e.resize(m);
    for (int i = 0; i < m; i++)
    {
        cin >> e[i].a >> e[i].b >> e[i].w;
        e[i].a--; e[i].b--;
    }

    int q;
    cin >> q;
    for (int qli = 0; qli < q; qli += SQ)
    {
        int qri = qli + SQ - 1;
        qri = min(qri, q - 1);

        vector<query> qr(qri - qli + 1);
        vector<bool> used(m);
        for (int i = 0; i < qr.size(); i++)
        {
            cin >> qr[i].qt >> qr[i].x >> qr[i].y;
            qr[i].x--;

            if (qr[i].qt == 1)
            {
                used[qr[i].x] = true;
            }
        }

        vector<int> eu, notu;
        for (int i = 0; i < m; i++)
        {
            if (used[i])
            {
                eu.push_back(i);
            }
            else
            {
                notu.push_back(i);
            }
        }
        sort(notu.begin(), notu.end(),
            [&](int x, int y)
            {
                return e[x].w < e[y].w;
            }
        );

        vector<vector<int>> add;
        vector<tuple<int, int, int>> ask;
        for (int i = 0; i < qr.size(); i++)
        {
            if (qr[i].qt == 1)
            {
                e[qr[i].x].w = qr[i].y;
                continue;
            }

            ask.push_back({ qr[i].y, qr[i].x, add.size() });
            add.push_back({});
            for (auto& j : eu)
            {
                if (e[j].w >= qr[i].y)
                {
                    add.back().push_back(j);
                }
            }
        }
        sort(ask.rbegin(), ask.rend());

        dsu kek(n);
        vector<int> ans(ask.size(), -1);
        for (auto& [w, ver, idx] : ask)
        {
            while (notu.size() && e[notu.back()].w >= w)
            {
                kek.unite(e[notu.back()].a, e[notu.back()].b);
                notu.pop_back();
            }

            for (auto& i : add[idx])
            {
                kek.unite(e[i].a, e[i].b);
            }
            ans[idx] = kek.get(ver);
            for (int _ = 0; _ < add[idx].size(); _++)
            {
                kek.ctrlz();
            }
        }
        for (int i = 0; i < ans.size(); i++)
        {
            cout << ans[i] << "\n";
        }
    }
}

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

    solve();

    return 0;
}

/*

























*/

Compilation message

bridges.cpp: In function 'void solve()':
bridges.cpp:114:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for (int i = 0; i < qr.size(); i++)
      |                         ~~^~~~~~~~~~~
bridges.cpp:146:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int i = 0; i < qr.size(); i++)
      |                         ~~^~~~~~~~~~~
bridges.cpp:181:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |             for (int _ = 0; _ < add[idx].size(); _++)
      |                             ~~^~~~~~~~~~~~~~~~~
bridges.cpp:186:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |         for (int i = 0; i < ans.size(); i++)
      |                         ~~^~~~~~~~~~~~

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	25 ms	1112 KB	Output is correct
4	Correct	3 ms	344 KB	Output is correct
5	Correct	11 ms	600 KB	Output is correct
6	Correct	13 ms	684 KB	Output is correct
7	Correct	21 ms	688 KB	Output is correct
8	Correct	20 ms	604 KB	Output is correct
9	Correct	29 ms	808 KB	Output is correct
10	Correct	26 ms	604 KB	Output is correct
11	Correct	26 ms	604 KB	Output is correct
12	Correct	25 ms	704 KB	Output is correct
13	Correct	36 ms	800 KB	Output is correct
14	Correct	24 ms	600 KB	Output is correct
15	Correct	24 ms	604 KB	Output is correct
16	Correct	25 ms	724 KB	Output is correct
17	Correct	30 ms	604 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1748 ms	8244 KB	Output is correct
2	Correct	1808 ms	8336 KB	Output is correct
3	Correct	1829 ms	8240 KB	Output is correct
4	Correct	1897 ms	8220 KB	Output is correct
5	Correct	1715 ms	8472 KB	Output is correct
6	Correct	2487 ms	9900 KB	Output is correct
7	Correct	2613 ms	9940 KB	Output is correct
8	Correct	2524 ms	9552 KB	Output is correct
9	Correct	25 ms	604 KB	Output is correct
10	Correct	1695 ms	9516 KB	Output is correct
11	Correct	1621 ms	8724 KB	Output is correct
12	Correct	1467 ms	8316 KB	Output is correct
13	Correct	1523 ms	8988 KB	Output is correct

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1444 ms	5816 KB	Output is correct
2	Correct	1249 ms	2952 KB	Output is correct
3	Correct	1753 ms	6088 KB	Output is correct
4	Correct	1395 ms	5608 KB	Output is correct
5	Correct	37 ms	604 KB	Output is correct
6	Correct	1594 ms	6072 KB	Output is correct
7	Correct	1280 ms	5508 KB	Output is correct
8	Correct	1109 ms	5272 KB	Output is correct
9	Correct	927 ms	5480 KB	Output is correct
10	Correct	803 ms	5244 KB	Output is correct
11	Correct	943 ms	5068 KB	Output is correct
12	Correct	780 ms	5008 KB	Output is correct

Subtask #4

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1843 ms	10824 KB	Output is correct
2	Correct	24 ms	604 KB	Output is correct
3	Correct	157 ms	7600 KB	Output is correct
4	Correct	79 ms	7660 KB	Output is correct
5	Correct	1178 ms	10776 KB	Output is correct
6	Correct	1801 ms	10808 KB	Output is correct
7	Correct	1113 ms	10756 KB	Output is correct
8	Correct	996 ms	7316 KB	Output is correct
9	Correct	1004 ms	7444 KB	Output is correct
10	Correct	1022 ms	7540 KB	Output is correct
11	Correct	1465 ms	10668 KB	Output is correct
12	Correct	1445 ms	10064 KB	Output is correct
13	Correct	1519 ms	10284 KB	Output is correct
14	Correct	1074 ms	11624 KB	Output is correct
15	Correct	1155 ms	10796 KB	Output is correct
16	Correct	1825 ms	11156 KB	Output is correct
17	Correct	1830 ms	11156 KB	Output is correct
18	Correct	1836 ms	11048 KB	Output is correct
19	Correct	1830 ms	10928 KB	Output is correct
20	Correct	1647 ms	10992 KB	Output is correct
21	Correct	1574 ms	10932 KB	Output is correct
22	Correct	1777 ms	10596 KB	Output is correct
23	Correct	1181 ms	9968 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1748 ms	8244 KB	Output is correct
2	Correct	1808 ms	8336 KB	Output is correct
3	Correct	1829 ms	8240 KB	Output is correct
4	Correct	1897 ms	8220 KB	Output is correct
5	Correct	1715 ms	8472 KB	Output is correct
6	Correct	2487 ms	9900 KB	Output is correct
7	Correct	2613 ms	9940 KB	Output is correct
8	Correct	2524 ms	9552 KB	Output is correct
9	Correct	25 ms	604 KB	Output is correct
10	Correct	1695 ms	9516 KB	Output is correct
11	Correct	1621 ms	8724 KB	Output is correct
12	Correct	1467 ms	8316 KB	Output is correct
13	Correct	1523 ms	8988 KB	Output is correct
14	Correct	1444 ms	5816 KB	Output is correct
15	Correct	1249 ms	2952 KB	Output is correct
16	Correct	1753 ms	6088 KB	Output is correct
17	Correct	1395 ms	5608 KB	Output is correct
18	Correct	37 ms	604 KB	Output is correct
19	Correct	1594 ms	6072 KB	Output is correct
20	Correct	1280 ms	5508 KB	Output is correct
21	Correct	1109 ms	5272 KB	Output is correct
22	Correct	927 ms	5480 KB	Output is correct
23	Correct	803 ms	5244 KB	Output is correct
24	Correct	943 ms	5068 KB	Output is correct
25	Correct	780 ms	5008 KB	Output is correct
26	Correct	1769 ms	8236 KB	Output is correct
27	Correct	2408 ms	8900 KB	Output is correct
28	Correct	1905 ms	8136 KB	Output is correct
29	Correct	1250 ms	7760 KB	Output is correct
30	Correct	2029 ms	8576 KB	Output is correct
31	Correct	2063 ms	8740 KB	Output is correct
32	Correct	2085 ms	8764 KB	Output is correct
33	Correct	1843 ms	7964 KB	Output is correct
34	Correct	1817 ms	8356 KB	Output is correct
35	Correct	1793 ms	8208 KB	Output is correct
36	Correct	1358 ms	7872 KB	Output is correct
37	Correct	1357 ms	7532 KB	Output is correct
38	Correct	1287 ms	7808 KB	Output is correct
39	Correct	1080 ms	7404 KB	Output is correct
40	Correct	1085 ms	7884 KB	Output is correct
41	Correct	1055 ms	7612 KB	Output is correct
42	Correct	1016 ms	7440 KB	Output is correct
43	Correct	993 ms	7508 KB	Output is correct
44	Correct	1008 ms	7788 KB	Output is correct

Subtask #6

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	25 ms	1112 KB	Output is correct
4	Correct	3 ms	344 KB	Output is correct
5	Correct	11 ms	600 KB	Output is correct
6	Correct	13 ms	684 KB	Output is correct
7	Correct	21 ms	688 KB	Output is correct
8	Correct	20 ms	604 KB	Output is correct
9	Correct	29 ms	808 KB	Output is correct
10	Correct	26 ms	604 KB	Output is correct
11	Correct	26 ms	604 KB	Output is correct
12	Correct	25 ms	704 KB	Output is correct
13	Correct	36 ms	800 KB	Output is correct
14	Correct	24 ms	600 KB	Output is correct
15	Correct	24 ms	604 KB	Output is correct
16	Correct	25 ms	724 KB	Output is correct
17	Correct	30 ms	604 KB	Output is correct
18	Correct	1748 ms	8244 KB	Output is correct
19	Correct	1808 ms	8336 KB	Output is correct
20	Correct	1829 ms	8240 KB	Output is correct
21	Correct	1897 ms	8220 KB	Output is correct
22	Correct	1715 ms	8472 KB	Output is correct
23	Correct	2487 ms	9900 KB	Output is correct
24	Correct	2613 ms	9940 KB	Output is correct
25	Correct	2524 ms	9552 KB	Output is correct
26	Correct	25 ms	604 KB	Output is correct
27	Correct	1695 ms	9516 KB	Output is correct
28	Correct	1621 ms	8724 KB	Output is correct
29	Correct	1467 ms	8316 KB	Output is correct
30	Correct	1523 ms	8988 KB	Output is correct
31	Correct	1444 ms	5816 KB	Output is correct
32	Correct	1249 ms	2952 KB	Output is correct
33	Correct	1753 ms	6088 KB	Output is correct
34	Correct	1395 ms	5608 KB	Output is correct
35	Correct	37 ms	604 KB	Output is correct
36	Correct	1594 ms	6072 KB	Output is correct
37	Correct	1280 ms	5508 KB	Output is correct
38	Correct	1109 ms	5272 KB	Output is correct
39	Correct	927 ms	5480 KB	Output is correct
40	Correct	803 ms	5244 KB	Output is correct
41	Correct	943 ms	5068 KB	Output is correct
42	Correct	780 ms	5008 KB	Output is correct
43	Correct	1843 ms	10824 KB	Output is correct
44	Correct	24 ms	604 KB	Output is correct
45	Correct	157 ms	7600 KB	Output is correct
46	Correct	79 ms	7660 KB	Output is correct
47	Correct	1178 ms	10776 KB	Output is correct
48	Correct	1801 ms	10808 KB	Output is correct
49	Correct	1113 ms	10756 KB	Output is correct
50	Correct	996 ms	7316 KB	Output is correct
51	Correct	1004 ms	7444 KB	Output is correct
52	Correct	1022 ms	7540 KB	Output is correct
53	Correct	1465 ms	10668 KB	Output is correct
54	Correct	1445 ms	10064 KB	Output is correct
55	Correct	1519 ms	10284 KB	Output is correct
56	Correct	1074 ms	11624 KB	Output is correct
57	Correct	1155 ms	10796 KB	Output is correct
58	Correct	1825 ms	11156 KB	Output is correct
59	Correct	1830 ms	11156 KB	Output is correct
60	Correct	1836 ms	11048 KB	Output is correct
61	Correct	1830 ms	10928 KB	Output is correct
62	Correct	1647 ms	10992 KB	Output is correct
63	Correct	1574 ms	10932 KB	Output is correct
64	Correct	1777 ms	10596 KB	Output is correct
65	Correct	1181 ms	9968 KB	Output is correct
66	Correct	1769 ms	8236 KB	Output is correct
67	Correct	2408 ms	8900 KB	Output is correct
68	Correct	1905 ms	8136 KB	Output is correct
69	Correct	1250 ms	7760 KB	Output is correct
70	Correct	2029 ms	8576 KB	Output is correct
71	Correct	2063 ms	8740 KB	Output is correct
72	Correct	2085 ms	8764 KB	Output is correct
73	Correct	1843 ms	7964 KB	Output is correct
74	Correct	1817 ms	8356 KB	Output is correct
75	Correct	1793 ms	8208 KB	Output is correct
76	Correct	1358 ms	7872 KB	Output is correct
77	Correct	1357 ms	7532 KB	Output is correct
78	Correct	1287 ms	7808 KB	Output is correct
79	Correct	1080 ms	7404 KB	Output is correct
80	Correct	1085 ms	7884 KB	Output is correct
81	Correct	1055 ms	7612 KB	Output is correct
82	Correct	1016 ms	7440 KB	Output is correct
83	Correct	993 ms	7508 KB	Output is correct
84	Correct	1008 ms	7788 KB	Output is correct
85	Correct	2161 ms	11980 KB	Output is correct
86	Correct	183 ms	9048 KB	Output is correct
87	Correct	108 ms	9672 KB	Output is correct
88	Correct	1381 ms	12068 KB	Output is correct
89	Correct	2151 ms	11572 KB	Output is correct
90	Correct	1439 ms	11764 KB	Output is correct
91	Correct	1783 ms	8140 KB	Output is correct
92	Correct	1786 ms	8268 KB	Output is correct
93	Correct	2557 ms	8884 KB	Output is correct
94	Correct	1837 ms	11264 KB	Output is correct
95	Correct	1939 ms	10832 KB	Output is correct
96	Correct	1819 ms	12344 KB	Output is correct
97	Correct	1121 ms	11356 KB	Output is correct
98	Correct	1145 ms	11420 KB	Output is correct
99	Correct	2269 ms	11956 KB	Output is correct
100	Correct	2315 ms	10900 KB	Output is correct
101	Correct	2371 ms	12308 KB	Output is correct
102	Correct	2343 ms	11332 KB	Output is correct
103	Correct	2112 ms	12688 KB	Output is correct
104	Correct	2062 ms	12296 KB	Output is correct
105	Correct	1609 ms	10744 KB	Output is correct
106	Correct	1405 ms	10624 KB	Output is correct
107	Correct	1769 ms	11084 KB	Output is correct
108	Correct	2164 ms	11664 KB	Output is correct
109	Correct	1409 ms	11192 KB	Output is correct