Submission #1095120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095120		ro9669	Bridges (APIO19_bridges)	C++17	0 / 100	3040 ms	4360 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 = 10000;

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

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}};
    }
    cin >> q;
    for (int i = 1 ; i <= q ; i++){
        int t , x , y;
        cin >> t >> x >> y;
        query[i] = {t , {x , y}};
    }
    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 <= m ; i++){
            id[i] = i;
            fa[i] = -1;
        }
        sort(id + 1 , id + m + 1 , [](int x , int y){
             return edge[x].fi > edge[y].fi;
        });
        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 = 0 ; x < sz(pos) ; x++){
            while (y + 1 <= m && edge[id[y + 1]].fi >= query[pos[x]].se.se){
                y++;
                if (del[y] == 0) unite(id[y] , 0);
            }
            for (int i = rig ; i >= lef ; i--){
                if (query[i].fi == 1) used[query[i].se.fi] = 0;
            }
            for (int i = pos[x] ; 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;
            }
            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:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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