Submission #1338830

#TimeUsernameProblemLanguageResultExecution timeMemory
1338830LudisseyBridges (APIO19_bridges)C++20
100 / 100
2691 ms4140 KiB
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

vector<int> parent;
vector<int> sz;
pair<int,int> szREV={-1,-1};
pair<int,int> parREV={-1,-1};
bool conserve=false;

int getParent(int x){
    if(parent[x]==x) return x;
    if(conserve) return getParent(parent[x]);
    else return (parent[x]=getParent(parent[x]));
}

void unite(int a, int b){
    a=getParent(a);
    b=getParent(b);
    if(a==b) return;
    if(sz[a]>sz[b]) swap(a,b);
    parREV={a,parent[a]};
    parent[a]=b;
    szREV={b,sz[b]};
    sz[b]+=sz[a];
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,q; cin >> n >> m;
    parent.resize(n);
    sz.resize(n);
    vector<pair<int,pair<int,int>>> edge(m);
    vector<pair<int,int>> se(m);
    for (int i = 0; i < m; i++)
    {
        int u,v,w; cin >> u >> v >> w; u--; v--;
        edge[i]={w,{u,v}};
        se[i]={w,i};
    }
    sort(rall(se));

    cin >> q;
    int sq=400;
    for (int _q = 0; _q < q; _q+=sq)
    {
        vector<pair<int,int>> se(m);
        for (int i = 0; i < m; i++) se[i]={edge[i].first,i};
        sort(rall(se));
        vector<pair<int,pair<int,int>>> query;
        vector<pair<int,pair<int,int>>> chg;
        vector<bool> used(m);
        for (int i = 0; i < n; i++)
        {
            parent[i]=i;
            sz[i]=1;
        }
        for (int i = 0; i < min(sq,q-_q); i++)
        {
            int t,a,b; cin >> t >> a >> b;
            if(t==1){
                used[a-1]=true;
                chg.push_back({i, {a-1,b}});
            }else{
                query.push_back({i,{a-1, b}});
            }
        }
        vector<int> ans(sz(query)+sz(chg),-1);
        vector<int> spec;
        for (int i = 0; i < m; i++)
        {
            if(used[i]) spec.push_back(i);
        }
        unordered_map<int,int> mod;
        sort(all(query), [](auto &a, auto &b){ return a.second.second>b.second.second; });
        int j=0;
        for (int i = 0; i < sz(query); i++)
        {
            conserve=false;
            while(j<m&&se[j].first>=query[i].second.second){
                if(!used[se[j].second]) unite(edge[se[j].second].second.first, edge[se[j].second].second.second);
                j++;
            }
            for (int k = 0; k < sz(spec); k++)
            {
                mod[spec[k]]=edge[spec[k]].first;
            }
            for (int k = 0; k < sz(chg); k++)
            {
                if(chg[k].first>=query[i].first) break;
                mod[chg[k].second.first]=chg[k].second.second; 
            }
            conserve=true;
            vector<pair<pair<int,int>,pair<int,int>>> rev;
            for (int k = 0; k < sz(spec); k++)
            {
                if(mod[spec[k]]<query[i].second.second) continue;
                szREV={-1,-1};
                parREV={-1,-1};
                unite(edge[spec[k]].second.first,edge[spec[k]].second.second);
                rev.push_back({szREV, parREV});
            }
            ans[query[i].first]=sz[getParent(query[i].second.first)];
            for (int k = sz(rev)-1; k >= 0; k--)
            {
                if(rev[k].first.first==-1) continue;
                sz[rev[k].first.first]=rev[k].first.second;
                parent[rev[k].second.first]=rev[k].second.second;
            }
        }
        for (int i = 0; i < sz(ans); i++)
        {
            if(ans[i]==-1) continue;
            cout << ans[i] << "\n";
        }
        for (auto i = 0; i < sz(chg); i++)
        {
            edge[chg[i].second.first].first=chg[i].second.second;
        }
        
    }
    
    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...