Submission #1160588

#TimeUsernameProblemLanguageResultExecution timeMemory
1160588MPGBridges (APIO19_bridges)C++20
59 / 100
3090 ms12140 KiB
//#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;}





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



int get(int v){
    if (par[v] == v)
        return v;
    return get(par[v]);
}
void merge(int v, int 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){
        int 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;
int mx = q / sq;
for (int i = 1; i < q + 1; i++){
    int a, b, c; cin >> a >> b >> c;
    qu[i / sq].pb({a, {b, c}});
}

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 <int, int>, int>> ask, ez, tmp; ask.clear(), ez.clear(); tmp.clear();
    vector <pair <int, int>> 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;
        }
        int 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...