oj.uz

답안 #484601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484601 2021-11-04T15:29:10 Z Lam_lai_cuoc_doi 다리 (APIO19_bridges) C++17
100 / 100
 1566 ms 11976 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
constexpr int block = 418;

//Ảo thật đấy
//Ông hoàng phân đoạn, bà chúa chia căn, ...

struct dsu
{
    int par[N];
    vector<pair<int, int>> snap;
    dsu()
    {
        memset(par, -1, sizeof par);
    }
    int findpar(int v)
    {
        while (par[v] > 0)
            v = par[v];
        return v;
    }
    void Merge(int u, int v)
    {
        u = findpar(u);
        v = findpar(v);
        if (u == v)
            return;

        if (par[u] < par[v])
            swap(u, v);

        par[v] += par[u];
        snap.emplace_back(u, par[u]);
        par[u] = v;
    }
    void RollBack(int sz)
    {
        while ((int)snap.size() > sz)
        {
            pair<int, int> c = snap.back();
            snap.pop_back();

            par[par[c.first]] -= c.second;
            par[c.first] = c.second;
        }
    }
} f;

int n, m, q;
int u[N], v[N], t[N], w[N];
int en[N], now[N], ans[N];
vector<int> Edge;

void Read()
{
    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        cin >> u[now[i] = i] >> v[i] >> w[i];
        t[i] = 1;
        Edge.emplace_back(i);
        en[i] = N;
    }

    cin >> q;

    for (int i = m + 1; i <= m + q; ++i)
    {
        cin >> t[i] >> u[i] >> w[i];

        if (t[i] == 1)
        {
            en[now[u[i]]] = i - 1;
            now[u[i]] = i;
            Edge.emplace_back(i);
            en[i] = N;

            v[i] = v[u[i]];
            u[i] = u[u[i]];
        }
    }
}

void Solve()
{
    sort(Edge.begin(), Edge.end(), [&](const int &x, const int &y)
         { return w[x] > w[y]; });

    for (int l = m + 1, r; l <= m + q; l += block)
    {
        r = min(m + q, l + block - 1);
        vector<int> fix, dyn, que;

        // There are at most (r - l) element in dyn

        for (int i = l; i <= r; ++i)
            if (t[i] == 2)
                que.emplace_back(i);

        for (auto i : Edge)
            if (i <= l && en[i] >= r)
                fix.emplace_back(i);
            else if (i <= r && en[i] >= l)
                dyn.emplace_back(i);

        sort(que.begin(), que.end(), [&](const int &x, const int &y)
             { return w[x] > w[y]; });

        // O((r - l) * (r - l) + m + q)

        int j = 0;
        for (auto i : que)
        {
            while (j < (int)fix.size() && w[fix[j]] >= w[i])
            {
                f.Merge(u[fix[j]], v[fix[j]]);
                ++j;
            }

            int tmp = f.snap.size();
            for (auto t : dyn)
                if (t <= i && en[t] >= i && w[t] >= w[i])
                    f.Merge(u[t], v[t]);

            ans[i] = -f.par[f.findpar(u[i])];

            f.RollBack(tmp);
        }

        f.RollBack(0);
    }

    for (int i = m + 1; i <= m + q; ++i)
        if (t[i] == 2)
            cout << ans[i] << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("palesta.INP", "r"))
    {
        freopen("paletsa.inp", "r", stdin);
        freopen("palesta.out", "w", stdout);
    }
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
11
-1 4
-4 2
-5 0
0 0
-3 -2
1 -2
5 -2
2 -3
-1 -4
1 -4
3 -4
*/

Compilation message

bridges.cpp: In function 'void read(T&)':
bridges.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
bridges.cpp: In function 'int32_t main()':
bridges.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen("paletsa.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen("palesta.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 19 ms 1620 KB Output is correct
4 Correct 4 ms 1356 KB Output is correct
5 Correct 15 ms 1552 KB Output is correct
6 Correct 11 ms 1548 KB Output is correct
7 Correct 16 ms 1484 KB Output is correct
8 Correct 15 ms 1544 KB Output is correct
9 Correct 14 ms 1484 KB Output is correct
10 Correct 15 ms 1560 KB Output is correct
11 Correct 14 ms 1484 KB Output is correct
12 Correct 15 ms 1540 KB Output is correct
13 Correct 18 ms 1668 KB Output is correct
14 Correct 18 ms 1560 KB Output is correct
15 Correct 17 ms 1544 KB Output is correct
16 Correct 13 ms 1484 KB Output is correct
17 Correct 13 ms 1472 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 967 ms 8764 KB Output is correct
2 Correct 971 ms 8868 KB Output is correct
3 Correct 962 ms 8664 KB Output is correct
4 Correct 1000 ms 8848 KB Output is correct
5 Correct 970 ms 8764 KB Output is correct
6 Correct 1202 ms 8532 KB Output is correct
7 Correct 1194 ms 8460 KB Output is correct
8 Correct 1212 ms 8760 KB Output is correct
9 Correct 31 ms 4144 KB Output is correct
10 Correct 761 ms 7640 KB Output is correct
11 Correct 755 ms 7656 KB Output is correct
12 Correct 675 ms 8420 KB Output is correct
13 Correct 948 ms 9132 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 7780 KB Output is correct
2 Correct 458 ms 5832 KB Output is correct
3 Correct 820 ms 7768 KB Output is correct
4 Correct 753 ms 8016 KB Output is correct
5 Correct 31 ms 4132 KB Output is correct
6 Correct 806 ms 7704 KB Output is correct
7 Correct 735 ms 7760 KB Output is correct
8 Correct 688 ms 7748 KB Output is correct
9 Correct 461 ms 7408 KB Output is correct
10 Correct 455 ms 7648 KB Output is correct
11 Correct 668 ms 7752 KB Output is correct
12 Correct 644 ms 7676 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1139 ms 10704 KB Output is correct
2 Correct 30 ms 4164 KB Output is correct
3 Correct 106 ms 7068 KB Output is correct
4 Correct 86 ms 6884 KB Output is correct
5 Correct 915 ms 9248 KB Output is correct
6 Correct 1103 ms 10960 KB Output is correct
7 Correct 919 ms 9336 KB Output is correct
8 Correct 548 ms 7936 KB Output is correct
9 Correct 538 ms 7824 KB Output is correct
10 Correct 548 ms 7636 KB Output is correct
11 Correct 894 ms 9292 KB Output is correct
12 Correct 845 ms 9624 KB Output is correct
13 Correct 885 ms 9176 KB Output is correct
14 Correct 913 ms 9220 KB Output is correct
15 Correct 939 ms 9136 KB Output is correct
16 Correct 1179 ms 10672 KB Output is correct
17 Correct 1185 ms 10596 KB Output is correct
18 Correct 1170 ms 10752 KB Output is correct
19 Correct 1143 ms 10504 KB Output is correct
20 Correct 1016 ms 9768 KB Output is correct
21 Correct 1038 ms 9508 KB Output is correct
22 Correct 1109 ms 10140 KB Output is correct
23 Correct 966 ms 8168 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 967 ms 8764 KB Output is correct
2 Correct 971 ms 8868 KB Output is correct
3 Correct 962 ms 8664 KB Output is correct
4 Correct 1000 ms 8848 KB Output is correct
5 Correct 970 ms 8764 KB Output is correct
6 Correct 1202 ms 8532 KB Output is correct
7 Correct 1194 ms 8460 KB Output is correct
8 Correct 1212 ms 8760 KB Output is correct
9 Correct 31 ms 4144 KB Output is correct
10 Correct 761 ms 7640 KB Output is correct
11 Correct 755 ms 7656 KB Output is correct
12 Correct 675 ms 8420 KB Output is correct
13 Correct 948 ms 9132 KB Output is correct
14 Correct 756 ms 7780 KB Output is correct
15 Correct 458 ms 5832 KB Output is correct
16 Correct 820 ms 7768 KB Output is correct
17 Correct 753 ms 8016 KB Output is correct
18 Correct 31 ms 4132 KB Output is correct
19 Correct 806 ms 7704 KB Output is correct
20 Correct 735 ms 7760 KB Output is correct
21 Correct 688 ms 7748 KB Output is correct
22 Correct 461 ms 7408 KB Output is correct
23 Correct 455 ms 7648 KB Output is correct
24 Correct 668 ms 7752 KB Output is correct
25 Correct 644 ms 7676 KB Output is correct
26 Correct 1041 ms 8644 KB Output is correct
27 Correct 1130 ms 8728 KB Output is correct
28 Correct 1056 ms 8888 KB Output is correct
29 Correct 913 ms 8776 KB Output is correct
30 Correct 1091 ms 8676 KB Output is correct
31 Correct 1109 ms 8488 KB Output is correct
32 Correct 1137 ms 8608 KB Output is correct
33 Correct 1004 ms 8856 KB Output is correct
34 Correct 1000 ms 8716 KB Output is correct
35 Correct 1020 ms 8840 KB Output is correct
36 Correct 906 ms 8712 KB Output is correct
37 Correct 907 ms 8844 KB Output is correct
38 Correct 905 ms 8740 KB Output is correct
39 Correct 648 ms 8548 KB Output is correct
40 Correct 659 ms 8488 KB Output is correct
41 Correct 641 ms 8460 KB Output is correct
42 Correct 813 ms 9232 KB Output is correct
43 Correct 821 ms 9236 KB Output is correct
44 Correct 820 ms 9040 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 19 ms 1620 KB Output is correct
4 Correct 4 ms 1356 KB Output is correct
5 Correct 15 ms 1552 KB Output is correct
6 Correct 11 ms 1548 KB Output is correct
7 Correct 16 ms 1484 KB Output is correct
8 Correct 15 ms 1544 KB Output is correct
9 Correct 14 ms 1484 KB Output is correct
10 Correct 15 ms 1560 KB Output is correct
11 Correct 14 ms 1484 KB Output is correct
12 Correct 15 ms 1540 KB Output is correct
13 Correct 18 ms 1668 KB Output is correct
14 Correct 18 ms 1560 KB Output is correct
15 Correct 17 ms 1544 KB Output is correct
16 Correct 13 ms 1484 KB Output is correct
17 Correct 13 ms 1472 KB Output is correct
18 Correct 967 ms 8764 KB Output is correct
19 Correct 971 ms 8868 KB Output is correct
20 Correct 962 ms 8664 KB Output is correct
21 Correct 1000 ms 8848 KB Output is correct
22 Correct 970 ms 8764 KB Output is correct
23 Correct 1202 ms 8532 KB Output is correct
24 Correct 1194 ms 8460 KB Output is correct
25 Correct 1212 ms 8760 KB Output is correct
26 Correct 31 ms 4144 KB Output is correct
27 Correct 761 ms 7640 KB Output is correct
28 Correct 755 ms 7656 KB Output is correct
29 Correct 675 ms 8420 KB Output is correct
30 Correct 948 ms 9132 KB Output is correct
31 Correct 756 ms 7780 KB Output is correct
32 Correct 458 ms 5832 KB Output is correct
33 Correct 820 ms 7768 KB Output is correct
34 Correct 753 ms 8016 KB Output is correct
35 Correct 31 ms 4132 KB Output is correct
36 Correct 806 ms 7704 KB Output is correct
37 Correct 735 ms 7760 KB Output is correct
38 Correct 688 ms 7748 KB Output is correct
39 Correct 461 ms 7408 KB Output is correct
40 Correct 455 ms 7648 KB Output is correct
41 Correct 668 ms 7752 KB Output is correct
42 Correct 644 ms 7676 KB Output is correct
43 Correct 1139 ms 10704 KB Output is correct
44 Correct 30 ms 4164 KB Output is correct
45 Correct 106 ms 7068 KB Output is correct
46 Correct 86 ms 6884 KB Output is correct
47 Correct 915 ms 9248 KB Output is correct
48 Correct 1103 ms 10960 KB Output is correct
49 Correct 919 ms 9336 KB Output is correct
50 Correct 548 ms 7936 KB Output is correct
51 Correct 538 ms 7824 KB Output is correct
52 Correct 548 ms 7636 KB Output is correct
53 Correct 894 ms 9292 KB Output is correct
54 Correct 845 ms 9624 KB Output is correct
55 Correct 885 ms 9176 KB Output is correct
56 Correct 913 ms 9220 KB Output is correct
57 Correct 939 ms 9136 KB Output is correct
58 Correct 1179 ms 10672 KB Output is correct
59 Correct 1185 ms 10596 KB Output is correct
60 Correct 1170 ms 10752 KB Output is correct
61 Correct 1143 ms 10504 KB Output is correct
62 Correct 1016 ms 9768 KB Output is correct
63 Correct 1038 ms 9508 KB Output is correct
64 Correct 1109 ms 10140 KB Output is correct
65 Correct 966 ms 8168 KB Output is correct
66 Correct 1041 ms 8644 KB Output is correct
67 Correct 1130 ms 8728 KB Output is correct
68 Correct 1056 ms 8888 KB Output is correct
69 Correct 913 ms 8776 KB Output is correct
70 Correct 1091 ms 8676 KB Output is correct
71 Correct 1109 ms 8488 KB Output is correct
72 Correct 1137 ms 8608 KB Output is correct
73 Correct 1004 ms 8856 KB Output is correct
74 Correct 1000 ms 8716 KB Output is correct
75 Correct 1020 ms 8840 KB Output is correct
76 Correct 906 ms 8712 KB Output is correct
77 Correct 907 ms 8844 KB Output is correct
78 Correct 905 ms 8740 KB Output is correct
79 Correct 648 ms 8548 KB Output is correct
80 Correct 659 ms 8488 KB Output is correct
81 Correct 641 ms 8460 KB Output is correct
82 Correct 813 ms 9232 KB Output is correct
83 Correct 821 ms 9236 KB Output is correct
84 Correct 820 ms 9040 KB Output is correct
85 Correct 1524 ms 11968 KB Output is correct
86 Correct 123 ms 6904 KB Output is correct
87 Correct 103 ms 7008 KB Output is correct
88 Correct 1209 ms 10356 KB Output is correct
89 Correct 1513 ms 11972 KB Output is correct
90 Correct 1208 ms 10540 KB Output is correct
91 Correct 1032 ms 8776 KB Output is correct
92 Correct 1000 ms 8828 KB Output is correct
93 Correct 1234 ms 8472 KB Output is correct
94 Correct 1364 ms 10380 KB Output is correct
95 Correct 1331 ms 10456 KB Output is correct
96 Correct 1453 ms 10336 KB Output is correct
97 Correct 1047 ms 9976 KB Output is correct
98 Correct 1212 ms 10560 KB Output is correct
99 Correct 1563 ms 11892 KB Output is correct
100 Correct 1561 ms 11976 KB Output is correct
101 Correct 1566 ms 11916 KB Output is correct
102 Correct 1534 ms 11936 KB Output is correct
103 Correct 1516 ms 11164 KB Output is correct
104 Correct 1499 ms 11232 KB Output is correct
105 Correct 1402 ms 11108 KB Output is correct
106 Correct 1219 ms 10532 KB Output is correct
107 Correct 1123 ms 10504 KB Output is correct
108 Correct 1526 ms 11724 KB Output is correct
109 Correct 1363 ms 9316 KB Output is correct