Submission #647578

#	Time	Username	Problem	Language	Result	Execution time	Memory
647578		baojiaopisu	Bridges (APIO19_bridges)	C++14	100 / 100	2769 ms	9964 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 1e5 + 10;

int par[N], ans[N], weight[N];
struct T {
    int u, v, pu, pv;
};
struct Edges {
    int u, v, w, id;

    bool operator < (const Edges & temp) const {
        return w > temp.w;
    }
} ed[N], e[N];
struct Q {
    int t, b, u, w;
} query[N];
int ec[N];
vector<T> line;
bool change[N];
int n, m;

int find_par(int u) {
    if(par[u] < 0) return u;
    return find_par(par[u]);
}

bool merge(int u, int v, int r) {
    u = find_par(u), v = find_par(v);
    if(u == v) return false;
    if(par[u] > par[v]) swap(u, v);
    if(!r) line.pb({u, v, par[u], par[v]});
    par[u] += par[v];
    par[v] = u;
    return true;
}
    
void RollBack() {
    while(line.size()) {
        int u = line.back().u, v = line.back().v;
        par[u] = line.back().pu;
        par[v] = line.back().pv;
        line.pop_back();
    }
}

void solsqrt(int L, int R) {
    sort(ed + 1, ed + 1 + m);
    for(int i = 1; i <= m; i++) change[i] = false;
    for(int i = 1; i <= n; i++) par[i] = -1;
    
    struct Data {
        int u, w, id;
    
        bool operator < (const Data & temp) const {
            return w > temp.w;
        }
    };
    vector<Data> q;

    for(int i = L; i <= R; i++) {
        if(query[i].t == 1) change[query[i].b] = true;
        else q.pb({query[i].u, query[i].w, i});
    }

    sort(all(q));
    int cnt = 0, cntc = 0;
    for(int i = 1; i <= m; i++) {
        if(!change[ed[i].id]) {
            e[++cnt] = ed[i];
        } else {
            ec[++cntc] = i;
        }
    }

    int iter = 1;
    for(auto x : q) {
        while(iter <= cnt && e[iter].w >= x.w) {
            merge(e[iter].u, e[iter].v, 1);
            ++iter;
        }

        for(int i = L; i <= x.id; i++) {
            if(query[i].t == 1) {
                weight[query[i].b] = query[i].w;
            }
        }

        for(int i = 1; i <= cntc; i++) {
            int w = (!weight[ed[ec[i]].id] ? ed[ec[i]].w : weight[ed[ec[i]].id]);
            if(w >= x.w) {
                merge(ed[ec[i]].u, ed[ec[i]].v, 0);
            }
        }

        ans[x.id] = -par[find_par(x.u)];
        RollBack();

        for(int i = L; i <= x.id; i++) {
            if(query[i].t == 1) {
                weight[query[i].b] = 0;
            }
        }
    }

    for(int i = L; i <= R; i++) {
        if(query[i].t == 1) {
            weight[query[i].b] = query[i].w;
        }
    }

    for(int i = 1; i <= m; i++) {
        if(weight[ed[i].id]) ed[i].w = weight[ed[i].id];
    }

    for(int i = L; i <= R; i++) {
        if(query[i].t == 1) {
            weight[query[i].b] = 0;
        }
    }
}

void solve() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v, w; cin >> u >> v >> w;
		ed[i] = {u, v, w, i};
	}

	int q; cin >> q;
	for(int i = 1; i <= q; i++) {
		cin >> query[i].t;
		if(query[i].t == 1) cin >> query[i].b >> query[i].w;
		else cin >> query[i].u >> query[i].w;
	}

	int s = sqrt(q);
	for(int i = 1; i <= q; i += s) {
		solsqrt(i, min(i + s - 1, q));
	}

    for(int i = 1; i <= q; i++) {
        if(ans[i]) cout << ans[i] << '\n';        
    }
}

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

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        solve();
    }
}   

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:217:17: warning: unused variable 'ddd' [-Wunused-variable]
  217 |     int tc = 1, ddd = 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