Submission #1160585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160585		MPG	Bridges (APIO19_bridges)	C++20	59 / 100	3092 ms	18716 KiB

bridges

//#pragma GCC optomize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 



#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
#define     max_heap priority_queue<pair <ll, pair <ll, ll>>>
#define     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
#define     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); 
#define     endl '\n'
#define     md(a) (a % mod + mod) % mod
#define     pb push_back
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769


ll const maxn = 2e5 + 123;
ll const inf = 2e18;
ll const loG = 23;
//ll const mod = 1e9 + 7;
ll const mod = 998244353;
ll const sq = 300;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}





ll n, m, q, w[maxn], sz[maxn], par[maxn], tim = 0, ans[maxn];
pair <ll, ll> yal[maxn];
vector <pair <ll, pair <ll, ll>>> qu[maxn];
vector <pair <pair <ll, ll>, ll>> chi;
bool mark[maxn];



ll get(ll v){
    if (par[v] == v)
        return v;
    return get(par[v]);
}
void merge(ll v, ll u){
    v = get(v), u = get(u);
    if (v == u){
        chi.pb({{v, u}, 0});
        return;
    }
    if (sz[v] < sz[u])
        swap(v, u);
    sz[v] += sz[u];
    par[u] = v;
    chi.pb({{v, u}, 1});
}

void roll(){
    if (chi.back().second){
        ll v = chi.back().first.first, u = chi.back().first.second;
        sz[v] -= sz[u];
        par[u] = u;
    }
    chi.pop_back();
}


void Solve(){

cin >> n >> m;
for (int i = 1; i < m + 1; i++){
    cin >> yal[i].first >> yal[i].second >> w[i];
}
cin >> q;
ll mx = 0;
for (int i = 1; i < q + 1; i++){
    ll a, b, c; cin >> a >> b >> c;
    qu[i / sq].pb({a, {b, c}});
    mx = max(mx, i / sq);
}

for (int i = 0; i < mx + 1; i++){
    for (int j = 1; j < m + 1; j++)
        mark[j] = 0;
    for (int j = 1; j < n + 1; j++){
        par[j] = j;
        sz[j] = 1;
    }
    chi.clear();

    vector <pair <pair <ll, ll>, ll>> ask, ez, tmp; ask.clear(), ez.clear(); tmp.clear();
    vector <pair <ll, ll>> edg; edg.clear(); 
    for (auto p : qu[i]){
        tim++;
        if (p.first == 2){
            ask.pb({{p.second.second, p.second.first}, tim});
        }
        else{
            mark[p.second.first] = 1;
            tmp.pb({{p.second.first, p.second.second}, tim});
        }
    }
    for (int j = 1; j < m + 1; j++){
        if (!mark[j]){
            //cout << "man " << j << ' ' << w[j] << endl;
            edg.pb({w[j], j});
        }
        else{
            ez.pb({{j, w[j]}, 0});
        }
    }
    for (auto p : tmp)
        ez.pb(p);
    
    sort(edg.begin(), edg.end());
    sort(ask.begin(), ask.end()); reverse(ask.begin(), ask.end());
    for (auto p : ask){
        //cout << p.first.first << ' ' << p.first.second <<  ' ' << p.second << " is asking" << endl;
        while (edg.size() && edg.back().first >= p.first.first){
            //cout << "added " << edg.back().second << ' ' << edg.back().first << endl;
            merge(yal[edg.back().second].first, yal[edg.back().second].second);
            edg.pop_back();
        }
        //cout << "gabl ez " << endl;
        // for (int i = 1; i < n + 1; i++)
        //     cout << i << ' ' << get(i) << endl;
        
        for (auto bah : ez){
            if (bah.second > p.second)
                break;
            w[bah.first.first] = bah.first.second;
        }
        ll cnt = 0;
        for (auto bah : ez){
            if (bah.second > p.second)
                break;
            //cout << "bahing " << bah.first.second << ' ' << bah.first.first << ' ' << bah.second << endl;
            if (w[bah.first.first] >= p.first.first){
                cnt++;
                //cout << "ok" << endl;
                merge(yal[bah.first.first].first, yal[bah.first.first].second);
            }
            // else
            //     cout << "NO" << endl;
        }
        // for (int i = 1; i < n + 1; i++)
        //     cout << i << ' ' << get(i) << endl;
        ans[p.second] = (sz[get(p.first.second)]);
        while (cnt--){
            roll();
        }
    }
    for (auto bah : ez)
        w[bah.first.first] = bah.first.second;
}

for (int i = 1; i < tim + 1; i++)
    if (ans[i])
        cout << ans[i] << endl;


}





int main(){
sariE;// filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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