제출 #898062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898062		phoenix	다리 (APIO19_bridges)	C++17	100 / 100	2017 ms	22816 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 = 700;
 
struct DSU {
    int p[N];
    int r[N];
    void init(int n) {
        for(int i = 1; i <= n; i++) 
            p[i] = i, r[i] = 1;
    }
    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];
pair<int, int> edges[M];

query q[Q / B + 10][B];
int q_sz[Q / B + 10];

upd u[Q / B + 10][B];
int u_sz[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(int point = 0; point < q_sz[i]; point++) {
            query c = q[i][point];
            mp[c.w] = 1;
        } 
        for(int point = 0; point < u_sz[i]; point++) {
            upd c = u[i][point];
            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(int point = 0; point < q_sz[i]; point++) {
            query c = q[i][point];
            c.w = mp[c.w];
            q[i][point] = c;
        } 
        for(int point = 0; point < u_sz[i]; point++) {
            upd c = u[i][point];
            c.r = mp[c.r];
            u[i][point] = c;
        }
    }
}
 
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++) {
        cin >> edges[i].first >> edges[i].second >> d[i];
    }
    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][ u_sz[i / B]++ ] = {b, r, i};
            
        } else {
            int s, w;
            cin >> s >> w;
            q[i / B][ q_sz[i / B]++ ] = {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(int point = 0; point < u_sz[buck]; point++) {
            upd c = u[buck][point];
            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], q[buck] + q_sz[buck], [](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_sz[buck] && q[buck][cur_query].w >= minw) {
                auto [s, w, inx] = q[buck][cur_query];

                for(int point = 0; point < u_sz[buck]; point++) {
                    upd cur_up = u[buck][point];
                    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(int point = 0; point < u_sz[buck]; point++) {
            upd x = u[buck][point];
            d[x.b] = x.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