Submission #872157

#	Time	Username	Problem	Language	Result	Execution time	Memory
872157		Kihihihi	Bridges (APIO19_bridges)	C++17	100 / 100	2568 ms	12736 KiB

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));

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

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;
    cin >> n >> m;
    vector<edge> e(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;
    int SQ = sqrt(n + m) * 3;
    for (int qil = 0; qil < q; qil += SQ)
    {
        int qir = qil + SQ - 1;
        qir = min(qir, q - 1);
        int qlen = qir - qil + 1;

        vector<bool> used(m);
        vector<tuple<int, int, int>> qr(qlen);
        for (int i = 0; i < qlen; i++)
        {
            int qt;
            cin >> qt;
            if (qt == 1)
            {
                int idx, nw;
                cin >> idx >> nw;
                idx--;
                used[idx] = true;
                qr[i] = { qt, idx, nw };
            }
            else
            {
                int ver, w;
                cin >> ver >> w;
                ver--;
                qr[i] = { qt, ver, w };
            }
        }

        vector<int> ch, rest;
        for (int i = 0; i < m; i++)
        {
            if (used[i])
            {
                ch.push_back(i);
            }
            else
            {
                rest.push_back(i);
            }
        }

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

            ask.push_back({ qy, qx, add.size() });
            add.push_back({});
            for (auto& j : ch)
            {
                if (e[j].w >= qy)
                {
                    add.back().push_back(j);
                }
            }
        }
        sort(ask.rbegin(), ask.rend());
        sort(rest.begin(), rest.end(),
            [&](int x, int y)
            {
                return e[x].w > e[y].w;
            }
        );

        dsu kek(n);
        vector<int> ans(ask.size());
        int ptr = 0;
        for (auto& [w, ver, idx] : ask)
        {
            while (ptr < rest.size() && e[rest[ptr]].w >= w)
            {
                kek.unite(e[rest[ptr]].a, e[rest[ptr]].b);
                ptr++;
            }

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

bridges.cpp: In function 'void solve()':
bridges.cpp:177:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |             while (ptr < rest.size() && e[rest[ptr]].w >= w)
      |                    ~~~~^~~~~~~~~~~~~
bridges.cpp:188:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |             for (int _ = 0; _ < add[idx].size(); _++)
      |                             ~~^~~~~~~~~~~~~~~~~
bridges.cpp:193:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |         for (int i = 0; i < ans.size(); i++)
      |                         ~~^~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27