제출 #1150559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150559		windowwife	Bridges (APIO19_bridges)	C++20	59 / 100	3094 ms	7364 KiB

bridges

#include <bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 2, blocksize = 320, mod = 998244353;
int n, m, q, u[maxn], v[maxn], w[maxn], t[maxn], x[maxn], y[maxn], ans[maxn];
bool changed[maxn], visited[maxn];
vector<int> unchanged, updates, query, good[blocksize], adj[maxn], vv;
struct DSU
{
    vector<int> par;
    void init (int n)
    {
        par.resize(n + 1, -1);
    }
    void reset ()
    {
        fill(par.begin(), par.end(), -1);
    }
    int find_set (int u)
    {
        if (par[u] < 0) return u;
        return (par[u] = find_set(par[u]));
    }
    void union_set (int u, int v)
    {
        int pu = find_set(u), pv = find_set(v);
        if (pu == pv) return;
        if (par[pu] > par[pv]) swap(pu, pv);
        par[pu] += par[pv];
        par[pv] = pu;
    }
}dsu;
bool cmp1 (int a, int b)
{
    return w[a] < w[b];
}
bool cmp2 (int a, int b)
{
    return y[a] > y[b];
}
void dfs (int u)
{
    visited[u] = true;
    vv.push_back(u);
    for (int v : adj[u])
    {
        if (visited[v]) continue;
        dfs(v);
    }
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    dsu.init(n);
    for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i];
    cin >> q;
    for (int b = 1; b <= blocksize; b++)
    {
        int l = (b - 1)*blocksize + 1, r = min(q, b*blocksize);
        unchanged.clear(); updates.clear(); query.clear();
        dsu.reset();
        for (int i = 1; i <= m; i++) changed[i] = false;
        for (int j = l; j <= r; j++)
        {
            good[j - l].clear();
            cin >> t[j] >> x[j] >> y[j];
            if (t[j] == 1)
            {
                changed[x[j]] = true;
                updates.push_back(x[j]);
            }
            else query.push_back(j);
        }
        for (int i = 1; i <= m; i++)
            if (changed[i] == false) unchanged.push_back(i);
        for (int j = l; j <= r; j++)
        {
            if (t[j] == 1) w[x[j]] = y[j];
            else
            {
                for (int i : updates)
                    if (w[i] >= y[j])
                        good[j - l].push_back(i);
            }
        }
        sort(unchanged.begin(), unchanged.end(), cmp1);
        sort(query.begin(), query.end(), cmp2);
        for (int j : query)
        {
            while (!unchanged.empty() && w[unchanged.back()] >= y[j])
            {
                dsu.union_set(u[unchanged.back()], v[unchanged.back()]);
                unchanged.pop_back();
            }
            for (int i : good[j - l])
            {
                int pu = dsu.find_set(u[i]), pv = dsu.find_set(v[i]);
                adj[pu].push_back(pv);
                adj[pv].push_back(pu);
            }
            dfs(dsu.find_set(x[j]));
            for (int i : vv)
            {
                ans[j] -= dsu.par[i];
                visited[i] = false;
            }
            vv.clear();
            for (int i : good[j - l])
            {
                int pu = dsu.find_set(u[i]), pv = dsu.find_set(v[i]);
                adj[pu].clear();
                adj[pv].clear();
            }
        }
        if (r == q) break;
    }
    for (int j = 1; j <= q; j++)
        if (t[j] == 2) cout << ans[j] << '\n';
}

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