Submission #391397

#	Time	Username	Problem	Language	Result	Execution time	Memory
391397		phathnv	Bridges (APIO19_bridges)	C++11	100 / 100	2594 ms	4576 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 5e4 + 7;
const int M = 1e5 + 7;
const int BLOCK_SIZE = 1200;

struct Edge{
    int u, v, c;
};

struct Query{
    int type, a, b;
};

struct Dsu{
    int root[N], sz[N];
    stack<int> his;
    void init(int n){
        for(int i = 1; i <= n; i++){
            root[i] = i;
            sz[i] = 1;
        }
        while (!his.empty())
            his.pop();
    }
    int findRoot(int u){
        if (u == root[u])
            return u;
        return findRoot(root[u]);
    }
    int getSz(int u){
        return sz[findRoot(u)];
    }
    void unite(int u, int v){
        u = findRoot(u);
        v = findRoot(v);
        if (u == v)
            return;
        if (sz[u] < sz[v])
            swap(u, v);
        root[v] = u;
        sz[u] += sz[v];
        his.push(v);
    }
    int backup(){
        return his.size();
    }
    void rollback(int ver){
        while ((int) his.size() > ver){
            int v = his.top();
            int u = root[v];
            root[v] = v;
            while (true){
                sz[u] -= sz[v];
                if (u == root[u])
                    break;
                u = root[u];
            }
            his.pop();
        }
    }
} dsu;

int n, m, q, ordEdge[M];
Edge eds[M];
bool changed[M];

void Process(const vector<Query> &queries){
    vector<int> ordType2;
    vector<pair<int, int>> changedEdges;
    for(int i = 1; i <= m; i++){
        changed[i] = 0;
        ordEdge[i] = i;
    }
    for(int i = 0; i < (int) queries.size(); i++)
        if (queries[i].type == 2){
            ordType2.push_back(i);
        } else {
            changed[queries[i].a] = 1;
            changedEdges.push_back({queries[i].a, eds[queries[i].a].c});
        }

    sort(ordType2.begin(), ordType2.end(), [&](const int &a, const int &b){
            return queries[a].b > queries[b].b;
        });
    sort(ordEdge + 1, ordEdge + 1 + m, [&](const int &a, const int &b){
            return eds[a].c > eds[b].c;
        });

    dsu.init(n);
    vector<pair<int, int>> answer;
    int ptr = 1;
    for(int ind : ordType2){
        int u = queries[ind].a;
        int c = queries[ind].b;
        while (ptr <= m && eds[ordEdge[ptr]].c >= c){
            if (!changed[ordEdge[ptr]])
                dsu.unite(eds[ordEdge[ptr]].u, eds[ordEdge[ptr]].v);
            ptr++;
        }
        int ver = dsu.backup();
        for(int i = 0; i < ind; i++)
            if (queries[i].type == 1)
                eds[queries[i].a].c = queries[i].b;
        for(auto p : changedEdges){
            if (eds[p.first].c >= c)
                dsu.unite(eds[p.first].u, eds[p.first].v);
        }
        answer.push_back({ind, dsu.getSz(u)});
        for(auto p : changedEdges)
            eds[p.first].c = p.second;
        dsu.rollback(ver);
    }
    sort(answer.begin(), answer.end());
    for(auto p : answer)
        cout << p.second << '\n';
    for(Query q : queries)
        if (q.type == 1)
            eds[q.a].c = q.b;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> eds[i].u >> eds[i].v >> eds[i].c;
    cin >> q;

    vector<Query> queries;
    for(int i = 1; i <= q; i++){
        Query query;
        cin >> query.type >> query.a >> query.b;
        queries.push_back(query);
        if (queries.size() == BLOCK_SIZE){
            Process(queries);
            queries.clear();
        }
    }
    Process(queries);
    queries.clear();

    return 0;
}

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