Hướng dẫn giải của Bedao Regular Contest 01 - HOGWARTS


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Bài toán: Cho ~n~ đỉnh và ~m~ cạnh, mỗi cạnh đều có trọng số là ~w_i~, ~q~ truy vấn yêu cầu

  • ~C~ ~i~ ~W~ là thay đổi trọng số đỉnh thứ ~i~ thành ~W~
  • ~D~ ~j~ là xóa đi cạnh thứ ~j~ trong đồ thị ban đầu ( đương nhiên cạnh này phải là cạnh xuất hiện trong đồ thị ngay từ đầu )

Ta cần đi tìm thành phần liên thông có tổng trọng số các đỉnh là lớn nhất trong các thành phần liên thông tồn tại tại thời điểm đó.

Nhận xét 1: Lật ngược lại bài toán, ta thực hiện ngược các truy vấn. Chính vì đã thực hiện ngược các truy vấn nên ta cần khôi phục lại đồ thị ban đầu, việc khôi phục bắt đầu từ đồ thị sau khi đã thực hiện ~q~ truy vấn. Biết rằng đồ thị sau khi đã thực hiện ~q~ truy vấn là đồ thị bị xóa hết cạnh ở thao tác ~D~ ~j~ và thay đổi hết trọng số đỉnh ở thao tác ~C~ ~i~ ~W~.

Nhận xét 2: Khi đã có đồ thị sau khi thực hiện ~q~ truy vấn, thao tác ~D~ ~j~ là xóa cạnh ~j~ giờ đây sẽ là thêm cạnh ~j~ vào đồ thị, tương tự thao tác ~C~ ~i~ ~W~ là biến từ trọng số ~w~ thành ~W~ giờ đây sẽ là biến từ trọng số ~W~ về lại trọng số ~w~. Do bài toán thực hiện offline nên ta sẽ phải lưu đáp án.

Gọi ~sum_u~ là tổng trọng số của thành phần liên thông có đỉnh u là đại diện

Thao tác ~D~ ~j~ thêm cạnh có thể thực hiện bằng DSU, vậy khi thêm một cạnh vào là ta nối đỉnh ~u~ và đỉnh ~v~ thuộc ~2~ thành phần liên thông khác nhau vào thành ~1~ thành phần liên thông

-> ~sum_u + sum_v~

Thao tác ~C~ ~i~ ~W~ sẽ là trực tiếp thay đổi trọng số của đỉnh ~i~, việc thay đổi trọng số của đỉnh ~i~ từ ~W~ về ~w~ cũng sẽ dẫn đến ~sum_i~ thay đổi một lượng từ ~W~ về ~w~

-> ~sum_i = sum_i - W~, ~sum_i = sum_i + w~

Vậy để biết thành phần liên thông chứa trọng số lớn nhất có thể duy trì bằng một Multiset.

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define _(x) (1LL<<(x))
#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define turn_all(x) (_(x)-1LL)
#define bitCnt(x) __builtin_popcountll(x)

#define int long long
#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 2E5;

int w[N+9], ans[N+9];
bool visited[N+9];
int n,m,q;

struct dataQuery
{
    char cmd;
    int u;
    int oldK;
    int numEdge;
    dataQuery(char _cmd = 'a',int _u = 0, int _oldK = 0, int _numEdge = 0)
    {
        cmd = _cmd;
        u = _u;
        oldK = _oldK;
        numEdge = _numEdge;
    }
};
vector<dataQuery> query;

struct dataEdge
{
    int u;
    int v;
    dataEdge(int _u = 0, int _v = 0)
    {
        u = _u;
        v = _v;
    }
};

vector<dataEdge> edge;
multiset<int> sumStored;

struct DSU
{
    int n;
    vector<int> root;
    vector<int> sum;
    DSU(int _n = 0)
    {
        n = _n;
        root.assign(n+9,-1);
        sum.assign(n+9,0);
    }

    void init(int n)
    {
        for (int i = 1;i <= n; ++i)
        {
            sum[i] = w[i];
            sumStored.insert(sum[i]);
        }
    }

    int find_root(int u)
    {
        if (root[u] < 0) return u;
        else
        {
            root[u] = find_root(root[u]);
            return root[u];
        }
    }

    void updateSum(int u,int v)
    {
        sumStored.erase(sumStored.find(sum[u]));
        sumStored.erase(sumStored.find(sum[v]));
        sum[u] += sum[v];
        sumStored.insert(sum[u]);
    }

    bool union_root(int u,int v)
    {
        u = find_root(u);
        v = find_root(v);
        if (u == v) return false;
        root[u] += root[v];
        root[v] = u;
        updateSum(u,v);
        return true;
    }
} myDSU(N);

signed main()
{
    fastIO

    cin>>n>>m>>q;

    for (int i = 1;i <= n; ++i) cin>>w[i];

    for (int i = 1;i <= m; ++i)
    {
        int u,v;
        cin>>u>>v;
        edge.push_back({u,v});
    }

    for (int i = 1;i <= q; ++i)
    {
        char cmd;
        cin>>cmd;
        if (cmd == 'D')
        {
            int numEdge;
            cin>>numEdge;
            visited[numEdge] = true;
            query.push_back({cmd,0,0,numEdge});
        }
        else
        {
            int u, k;
            cin>>u>>k;
            query.push_back({cmd,u,w[u],0});
            w[u] = k;
        }
    }

    myDSU.init(n);

    for (int i = 1;i <= m; ++i)
        if (visited[i] == false)
        {
            int u = edge[i-1].u;
            int v = edge[i-1].v;
            myDSU.union_root(u,v);
        }

    for (int i = q;i >= 1; --i)
    {
        char cmd = query[i-1].cmd;
        ans[i] = *(sumStored.rbegin());
        if (cmd == 'D')
        {
            int numEdge = query[i-1].numEdge;
            int u = edge[numEdge-1].u;
            int v = edge[numEdge-1].v;
            myDSU.union_root(u,v);
        }
        else if (cmd == 'C')
        {
            int u = query[i-1].u;
            int oldK = query[i-1].oldK;

            int p = myDSU.find_root(u);
            sumStored.erase(sumStored.find(myDSU.sum[p]));
            myDSU.sum[p] -= w[u];
            w[u] = oldK;
            myDSU.sum[p] += w[u];
            sumStored.insert(myDSU.sum[p]);
        }
    }

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.