제출 #862580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862580		mraron	Bridges (APIO19_bridges)	C++14	100 / 100	2699 ms	17972 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

struct edge {
    int a,b,c;
    int ind;
} edgs[100001];

struct query {
    int typ;
    int x,y;
} qs[100010];


int sz[100010], par[100010];
vector<int> adj[100010];

int volt[100010], cur=0;

void dfs(int x, int& ans) {
    volt[x]=cur;
    ans+=sz[x];
    for(int i:adj[x]) {
        if(volt[i]<cur) {
            dfs(i, ans);
        }
    }
}

int n,m;
void init() {
    fill(sz+1, sz+n+1, 1);
    fill(par+1, par+n+1, -1);
}

int get(int x) {
    if(par[x]==-1) return x;
    return par[x]=get(par[x]);
}

void merge(int x, int y) {
    int px=get(x), py=get(y);
    if(px!=py) {
        par[px]=py;
        sz[py]+=sz[px];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;
    for(int i=0;i<m;++i) {
        cin>>edgs[i].a>>edgs[i].b>>edgs[i].c;
        edgs[i].ind=i;
    }
    
    int q;
    cin>>q;
    for(int i=0;i<q;++i) {
        cin>>qs[i].typ>>qs[i].x>>qs[i].y;
        if(qs[i].typ==1) qs[i].x--;
    }
    
    vector<int> results(q);

    const int blksz=500;
    for(int L=0;;L+=blksz) {
        int R=min(q-1, L+blksz-1);
        if(L>=q) break ;
        vector<bool> changedHere(m);
        vector<int> asked, bridges;
        for(int i=L;i<=R;++i) {
            if(qs[i].typ==1) changedHere[qs[i].x]=true;
            else asked.push_back(i);
        }
        
        for(int i=0;i<m;++i) {
            if(!changedHere[i]) {
                bridges.push_back(i);
            }
        }
        
        sort(asked.begin(), asked.end(), [&](int x, int y) -> bool {
            return qs[x].y>qs[y].y;
        });
        sort(bridges.begin(), bridges.end(), [&](int x, int y) -> bool {
            return edgs[x].c>edgs[y].c;
        });
        
        int ind=0;
        vector<int> last(m, -1);
        init();
        for(int i=0;i<(int)asked.size();++i) {
            while(ind<(int)bridges.size() && edgs[bridges[ind]].c>=qs[asked[i]].y) {
                merge(edgs[bridges[ind]].a, edgs[bridges[ind]].b);
                ind++;
            }
            
            vector<int> lst;
            for(int j=asked[i];j>=L;--j) {
                if(qs[j].typ==1) {
                    if(last[qs[j].x]!=i && qs[j].y>=qs[asked[i]].y) {
                        //~ cerr<<asked[i]<<" "<<j<<"firstcase\n";
                        int a=get(edgs[qs[j].x].a), b=get(edgs[qs[j].x].b);
                        if(a!=b) {
                            adj[a].push_back(b);
                            adj[b].push_back(a);
                            lst.push_back(a);
                            lst.push_back(b);
                        }
                    }
                    last[qs[j].x]=i;
                }
            }
            for(int j=asked[i]+1;j<=R;++j) {
                if(qs[j].typ==1 && last[qs[j].x]!=i) {                    
                    if(edgs[qs[j].x].c>=qs[asked[i]].y) {
                        int a=get(edgs[qs[j].x].a), b=get(edgs[qs[j].x].b);
                        if(a!=b) {
                            adj[a].push_back(b);
                            adj[b].push_back(a);
                            lst.push_back(a);
                            lst.push_back(b);
                        }
                    }
                    last[qs[j].x]=i;
                }
            }
            
            cur++;
            //~ cerr<<"NEED: "<<get(qs[asked[i]].x)<<" "<<asked[i]<<"\n";
            dfs(get(qs[asked[i]].x), results[asked[i]]);
            for(int i:lst) adj[i].clear();
        }
        
        for(int i=L;i<=R;++i) {
            if(qs[i].typ==1) edgs[qs[i].x].c=qs[i].y;
        }
    }
    
    for(int i=0;i<q;++i) if(qs[i].typ==2) cout<<results[i]<<"\n";
    return 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