Submission #898054

#	Time	Username	Problem	Language	Result	Execution time	Memory
898054		phoenix	Bridges (APIO19_bridges)	C++17	100 / 100	1567 ms	23504 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 50000 + 10;
const int M = 100000 + 10;
const int Q = 100000 + 10;
const int B = 800;

struct DSU {
    vector<int> p;
    vector<int> r;
    void init(int n) {
        p.assign(n + 1, 0);
        r.assign(n + 1, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        return p[x] = (p[x] == x ? x : find(p[x]));
    }
    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if(u == v) return;
        if(r[u] < r[v]) swap(u, v);
        r[u] += r[v];
        p[v] = u;
    }
};

struct query {
    int s, w, i;
};
struct upd {
    int b, r, i;
};

int n, m, q_len;

int d[M + 1];
vector<pair<int, int>> edges = {{0, 0}};
vector<query> q[Q / B + 10];
vector<upd> u[Q / B + 10];

int MAX_W = 0;
vector<int> e_sorted[M + Q + 10];

void compress() {
    map<int, int> mp;
    for(int i = 1; i <= m; i++) 
        mp[d[i]] = 1;
    for(int i = 0; i <= (q_len - 1) / B; i++) {
        for(auto c : q[i]) 
            mp[c.w] = 1;
        for(auto c : u[i])
            mp[c.r] = 1;
    }
    for(auto &c : mp)
        c.second = MAX_W ++;
    for(int i = 1; i <= m; i++)
        d[i] = mp[d[i]];
    for(int i = 0; i <= (q_len - 1) / B; i++) {
        for(auto &c : q[i])
            c.w = mp[c.w];
        for(auto &c : u[i])
            c.r = mp[c.r];
    }
}

vector<int> g[N];
DSU ds;

bool vis[N];

int dfs(int s) {
    vis[s] = true;
    int res = ds.r[s];
    for(int to : g[s]) {
        if(vis[to]) continue;
        res += dfs(to);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("test.txt", "r", stdin);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v >> d[i];
        edges.push_back({u, v});
    }
    cin >> q_len;  
    vector<int> res(q_len, -1); 
    for(int i = 0; i < q_len; i++) {
        int type;
        cin >> type;
        if(type == 1) {
            int b, r;
            cin >> b >> r;
            u[i / B].push_back({b, r, i});
        } else {
            int s, w;
            cin >> s >> w;
            q[i / B].push_back({s, w, i});
        }   
    }
    compress();
    for(int buck = 0; buck <= (q_len - 1) / B; buck++) {
        int d_changed[m + 1] = {};
        bool is_changed[m + 1] = {};
        vector<int> changed;
        for(auto c : u[buck]) {
            if(!is_changed[c.b]) 
                changed.push_back(c.b);
            is_changed[c.b] = true;
            d_changed[c.b] = d[c.b];
        }

        for(int i = 1; i <= m; i++) {
            if(!is_changed[i]) {
                e_sorted[d[i]].push_back(i);
            }
        }
        sort(q[buck].begin(), q[buck].end(), [](query a, query b) {
            return (a.w > b.w);
        });   
        ds.init(n + 1);
        int cur_query = 0;
        for(int minw = MAX_W - 1; minw >= 0; minw--) {
            for(int e_i : e_sorted[minw]) 
                ds.unite(edges[e_i].first, edges[e_i].second);
            while(cur_query < (int)q[buck].size() && q[buck][cur_query].w >= minw) {
                auto [s, w, inx] = q[buck][cur_query];
                for(auto cur_up : u[buck]) {
                    if(cur_up.i > inx) break;
                    d_changed[cur_up.b] = cur_up.r;
                } 
                for(int e_i : changed) {
                    if(d_changed[e_i] < w) continue;
                    auto [u, v] = edges[e_i];
                    u = ds.find(u), v = ds.find(v);
                    g[u].push_back(v);
                    g[v].push_back(u);
                }
                s = ds.find(s);
                res[inx] = dfs(s);

                for(int e_i : changed) {
                    d_changed[e_i] = d[e_i];
                    auto [u, v] = edges[e_i];
                    u = ds.find(u), v = ds.find(v);
                    vis[u] = 0;
                    vis[v] = 0;
                    g[u].clear();
                    g[v].clear();
                }
                vis[s] = 0;

                cur_query++;
            }
            e_sorted[minw].clear();
        }
        for(auto upd : u[buck])
            d[upd.b] = upd.r;
    }
    
    for(int i = 0; i < q_len; i++) 
        if(res[i] != -1)
            cout << res[i] << '\n';
}

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