Submission #1095184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095184		ro9669	Bridges (APIO19_bridges)	C++17	100 / 100	1985 ms	17424 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(1e5)+7;
const int block_size = 320;

int n , m , q;
pair<int , ii> edge[maxN] , query[maxN];
int fa[maxN] , res[maxN];
bool del[maxN] , used[maxN];
vector<pair<ii , ii>> event;
vector<int> val , g[2 * maxN];

int root(int x){
    if (fa[x] < 0) return x; else return root(fa[x]);
}

void unite(int u , int v , int t){
    u = root(u);
    v = root(v);
    if (u == v) return;
    if (t == 1){
        event.push_back({{u , fa[u]} , {v , fa[v]}});
    }
    if (-fa[u] < -fa[v]) swap(u , v);
    fa[u] += fa[v];
    fa[v] = u;
}

void unite(int id , int t){
    unite(edge[id].se.fi , edge[id].se.se , t);
}

void rollback(){
    while (event.empty() == 0){
        auto it = event.back(); event.pop_back();
        fa[it.fi.fi] = it.fi.se;
        fa[it.se.fi] = it.se.se;
    }
}

void solve(){
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        edge[i] = {w , {u , v}};
        val.push_back(w);
    }
    cin >> q;
    for (int i = 1 ; i <= q ; i++){
        int t , x , y;
        cin >> t >> x >> y;
        query[i] = {t , {x , y}};
        if (t == 1){
            val.push_back(y);
        }
    }
    unq(val);
    for (int i = 1 ; i <= m ; i++){
        g[lower_bound(all(val) , edge[i].fi) - val.begin()].push_back(i);
    }
    for (int t = 1 ; t <= (q + block_size - 1) / block_size ; t++){
        int lef = (t - 1) * block_size + 1;
        int rig = min(t * block_size , q);
        for (int i = 1 ; i <= n ; i++) fa[i] = -1;
        vector<int> pos;
        for (int i = lef ; i <= rig ; i++){
            if (query[i].fi == 1){
                del[query[i].se.fi] = 1;
            }
            else{
                pos.push_back(i);
            }
        }
        sort(all(pos) , [](int x , int y){
             return query[x].se.se > query[y].se.se;
        });
        for (int x = 0 , y = sz(val) ; x < sz(pos) ; x++){
            while (y - 1 >= 0 && val[y - 1] >= query[pos[x]].se.se){
                y--;
                for (int id : g[y]){
                    if (del[id] == 0 && edge[id].fi == val[y]){
                        unite(id , 0);
                    }
                }
            }
            for (int i = rig ; i >= lef ; i--){
                if (query[i].fi == 1) used[query[i].se.fi] = 0;
            }
            for (int i = pos[x] - 1 ; i >= lef ; i--){
                if (query[i].fi == 1 && used[query[i].se.fi] == 0){
                    if (query[i].se.se >= query[pos[x]].se.se) unite(query[i].se.fi , 1);
                    used[query[i].se.fi] = 1;
                }
            }
            for (int i = pos[x] + 1 ; i <= rig ; i++){
                if (query[i].fi == 1 && used[query[i].se.fi] == 0){
                    if (edge[query[i].se.fi].fi >= query[pos[x]].se.se){
                        unite(query[i].se.fi , 1);
                    }
                    used[query[i].se.fi] = 1;
                }
            }
            res[pos[x]] = -fa[root(query[pos[x]].se.fi)];
            rollback();
        }
        for (int i = lef ; i <= rig ; i++){
            if (query[i].fi == 1){
                del[query[i].se.fi] = 0;
                edge[query[i].se.fi].fi = query[i].se.se;
                g[lower_bound(all(val) , edge[query[i].se.fi].fi) - val.begin()].push_back(query[i].se.fi);
            }
            else{
                cout << res[i] << "\n";
            }
        }
    }
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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