Submission #484601

#	Time	Username	Problem	Language	Result	Execution time	Memory
484601		Lam_lai_cuoc_doi	Bridges (APIO19_bridges)	C++17	100 / 100	1566 ms	11976 KiB

bridges

#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 (stderr)

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 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27