제출 #1367133

#제출 시각아이디문제언어결과실행 시간메모리
1367133po_rag526다리 (APIO19_bridges)C++20
0 / 100
3094 ms15328 KiB
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define bp '\n'
#define vp cout<<'\n';
#define all(A) A.begin(),A.end()
using pii=pair<int,int>;
const int MOD=1e9+7;
const int MNLL=-1e18;
const int MXLL=1e18;
const int N=5e4+10;
vector<vector<pii>>a(N);
vector<array<int,3>>edge;
vector<array<int,4>>query;
int n,k,l,r,x,q,m;
int BFS(int src,int d){
    vector<int>vst(n+10,0);
    queue<int>q;
    int cnt=0;
    q.emplace(src);
    while (!q.empty())
    {
        src=q.front();
        q.pop();
        if(vst[src])continue;
        vst[src]=1;
        ++cnt;
        for(auto&[e,w]:a[src]){
            if(w<d or vst[e])continue;
            q.emplace(e);
        }
    }
    return cnt;
}
void type1(){
    for(auto&[x,l,r,id]:query){
        if(x==1){
            auto[u,v,w]=edge[l-1];
            edge[l-1]={u,v,r};
            a[u].erase(find(all(a[u]),make_pair(v,w)));
            a[u].emplace_back(v,r);
        }else{
            cout<<BFS(l,r)<<'\n';
        }
    }
}
struct DSU{
    vector<int>par,sz;
    DSU(int n):par(n+10),sz(n+10,1){
        iota(all(par),0);
    }
    int Find(int a){
        return par[a]==a?a:par[a]=Find(par[a]);
    }
    void Union(int a,int b){
        a=Find(a);
        b=Find(b);
        if(a==b)return;
        if(sz[b]>sz[a])swap(a,b);
        par[b]=a;
        sz[a]+=sz[b];
    }
};
void type4(){
    DSU dsu(n+10);
    vector<int>ans(q);
    for(auto&[x,l,r,id]:query){
        swap(x,r);
    }
    for(auto&[l,r,x]:edge){
        swap(l,x);
    }
    sort(all(query));
    sort(all(edge));
    int j=0;
    for(auto&[r,l,x,id]:query){
        while(j<m and edge[j][0]<=r){
            //cout<<"edge : "<<edge[j][2]<<' '<<edge[j][1]<<' '<<edge[j][0]<<'\n';
            dsu.Union(edge[j][1],edge[j][2]);
            ++j;
        }
        ans[id]=dsu.sz[dsu.Find(l)];
        //cout<<"-> "<<id<<' '<<l<<' '<<r<<'\n';
    }
    for(auto&e:ans){
        cout<<e<<'\n';
    }
}
//void type2(){}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int t1=0,t2=1,t4=1;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        cin>>l>>r>>x;
        edge.push_back({l,r,x});
        a[l].emplace_back(r,x);
        a[r].emplace_back(l,x);
        if(l+1!=r){
            t2=0;
        }
    }
    cin>>q;
    for(int i=0;i<q;++i){
        cin>>x>>l>>r;
        query.push_back({x,l,r,i});
        if(x==1){
            t4=0;
        }
    }
    type1();
}

/*

*/
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…