Submission #1361461

#TimeUsernameProblemLanguageResultExecution timeMemory
1361461AMel0nBridges (APIO19_bridges)C++20
16 / 100
3092 ms8236 KiB
#include <bits/stdc++.h>
using namespace std;
const int K = 300;

int N, M, Q;
vector<int> res;

struct e { 
    int w, u, v; 
    bool operator<(const e &o) const {
        return w < o.w;
    }
};
vector<e> edge;
priority_queue<e> mst, mstemp;
unordered_set<int> changed;
vector<pair<int,int>> changes; // qi: ei, w

struct q {int t, v, w;};
vector<q> query;
vector<int> sortedq;

int cnt;
struct h {int t, i, v;};
vector<h> history;
vector<int> par, sz;
int find(int v) {return par[v] == v ? v : find(par[v]);}
void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return ;
    if (sz[a] < sz[b]) swap(a, b);
    history.push_back({1, a, sz[a]});
    history.push_back({0, b, par[b]});
    cnt += 2;
    par[b] = a;
    sz[a] += sz[b];
}
void rollback(int k) {
    while(k--) {
        if (history.back().t) sz[history.back().i] = history.back().v;
        else par[history.back().i] = history.back().v;
        history.pop_back();
    }
}

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M;
    edge.resize(M);
    for(int i = 0; i < M; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
        edge[i].u--, edge[i].v--;
    }
    cin >> Q;
    query.resize(Q), res.resize(Q, -1), changes.resize(Q, {-1, -1});
    for(int i = 0; i < Q; i++) {
        cin >> query[i].t >> query[i].v >> query[i].w;
        query[i].v--;
    }
    for(int q = 0; q < Q; q += K) {
        changed.clear(), mst = {}, sortedq.clear();
        history.clear(), sz.assign(N, 1), par.assign(N, 0); iota(par.begin(), par.end(), 0);
        for(int j = q; j < min(q + K, Q); j++) {
            if (query[j].t == 1) {
                changed.insert(query[j].v);
                changes[j] = {query[j].v, query[j].w};
            } else sortedq.push_back(j);
        }
        for(int j = 0; j < M; j++) if (!changed.count(j)) mst.push(edge[j]);
        sort(sortedq.begin(), sortedq.end(), [&](const int &a, const int &b) {return query[a].w > query[b].w;});
        for(int &i: sortedq) {
            mstemp = {};
            for(int j = q; j < i; j++) {
                if (changes[j].first != -1) mstemp.push({changes[j].second, edge[changes[j].first].u, edge[changes[j].first].v});
            }
            for(int j = i; j < min(q + K, Q); j++) {
                if (changes[j].first != -1) mstemp.push({edge[changes[j].first].w, edge[changes[j].first].u, edge[changes[j].first].v});
            }
            while(mst.size() && mst.top().w >= query[i].w) {
                merge(mst.top().u, mst.top().v);
                mst.pop();
            }
            cnt = 0;
            while(mstemp.size() && mstemp.top().w >= query[i].w) {
                merge(mstemp.top().u, mstemp.top().v);
                mstemp.pop();
            }
            res[i] = sz[find(query[i].v)];
            rollback(cnt);
        }

        for(int j = q; j < min(q + K, Q); j++) {
            if (changes[j].first != -1) edge[changes[j].first].w = changes[j].second;
        }
    }
    for(int &i: res) if (i != -1) cout << i << endl;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...