제출 #872134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872134		Kihihihi	다리 (APIO19_bridges)	C++17	30 / 100	3050 ms	16560 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));

const long long INF = 1e18, MOD = 1e9 + 7;

const long long SQ = 300;

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

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

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

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

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

    void unite(long long a, long long 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();
    }

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

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

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

        vector<query> qr(qri - qli + 1);
        for (long long i = 0; i < qr.size(); i++)
        {
            cin >> qr[i].qt >> qr[i].x >> qr[i].y;
            qr[i].x--;
        }
        
        vector<bool> used(m);
        vector<long long> ord;
        for (long long i = 0; i < qr.size(); i++)
        {
            if (qr[i].qt == 1)
            {
                used[qr[i].x] = true;
            }
            else
            {
                ord.push_back(i);
            }
        }
        sort(ord.begin(), ord.end(),
            [&](long long x, long long y)
            {
                return qr[x].y > qr[y].y;
            }
        );

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

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

            for (auto& i : eu)
            {
                used[i] = false;
            }
            long long cnte = 0;
            for (long long i = idx - 1; i > -1; i--)
            {
                if (qr[i].qt == 2 || used[qr[i].x])
                {
                    continue;
                }

                if (qr[i].y >= w)
                {
                    cnte++;
                    kek.unite(e[qr[i].x].a, e[qr[i].x].b);
                }
                used[qr[i].x] = true;
            }
            for (auto& i : eu)
            {
                if (used[i])
                {
                    continue;
                }

                if (e[i].w >= w)
                {
                    cnte++;
                    kek.unite(e[i].a, e[i].b);
                }
            }
            ans[idx] = kek.get(ver);

            while (cnte)
            {
                kek.ctrlz();
                cnte--;
            }
        }
        for (long long i = 0; i < ans.size(); i++)
        {
            if (ans[i] == -1)
            {
                continue;
            }

            cout << ans[i] << "\n";
        }

        for (long long i = 0; i < qr.size(); i++)
        {
            if (qr[i].qt == 1)
            {
                e[qr[i].x].w = qr[i].y;
            }
        }
    }
}

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

    solve();

    return 0;
}

/*

























*/

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'void solve()':
bridges.cpp:115:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (long long i = 0; i < qr.size(); i++)
      |                               ~~^~~~~~~~~~~
bridges.cpp:123:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (long long i = 0; i < qr.size(); i++)
      |                               ~~^~~~~~~~~~~
bridges.cpp:211:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |         for (long long i = 0; i < ans.size(); i++)
      |                               ~~^~~~~~~~~~~~
bridges.cpp:221:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |         for (long long i = 0; i < qr.size(); i++)
      |                               ~~^~~~~~~~~~~

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