Submission #552763

#	Time	Username	Problem	Language	Result	Execution time	Memory
552763		jjaewon	Bridges (APIO19_bridges)	C++17	0 / 100	3091 ms	9532 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;

#define SZ 700

struct DATA{
    //type 0: edge, type 1: query 1, type 2: query 2
    int type,idx,u,v,d;
    bool operator<(const DATA& p) const{ return d==p.d?type<p.type:d<p.d; }
}edge[100010];
vector<DATA> query;
int N,M,Q,ans[100010];

int p[50010],sz[50010];
stack<pii> st;
int find(int x){ return x==p[x]?x:find(p[x]); }
bool merge(int x,int y,bool undo){
    x=find(x); y=find(y);
    if(x==y) return 0;
    if(sz[x]<sz[y]) swap(x,y);
    sz[x]+=sz[y];
    p[y]=x;
    if(undo) st.push({x,y});
    return 1;
}

void solve(){
    vector<DATA> v;
    bool used[100010]={0};
    for(auto i:query){
        if(i.type==1) used[i.idx]=1;
        else if(i.type==2) v.push_back(i);
    }
    for(auto i:edge) if(!used[i.idx]) v.push_back(i);
    sort(all(v));
    reverse(all(v));
    for(int i=1;i<=N;i++) p[i]=i, sz[i]=1;
    for(auto i:v){
        if(i.type==0) merge(i.u,i.v,0);
        else{
            bool flag=0;
            for(auto j:query){
                if(i.idx==j.idx) flag=1;
                if(j.type==1){
                    if((!flag&&j.d>=i.d)||(flag&&edge[j.u].d>=i.d))
                        merge(edge[j.u].u,edge[j.u].v,1);
                }
            }
            ans[i.idx]=sz[find(i.u)];
            while(!st.empty()){
                auto [x,y]=st.top();
                sz[x]-=sz[y];
                p[y]=y;
                st.pop();
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1;i<=M;i++){
        int u,v,d; cin>>u>>v>>d;
        edge[i]={0,i,u,v,d};
    }
    cin>>Q;
    for(int i=1;i<=Q;i++){
        int t,a,b; cin>>t>>a>>b;
        query.push_back({t,i,a,0,b});
    }
    solve();
    for(int i=1;i<=Q;i++) if(ans[i]>0) cout<<ans[i]<<endl;
    return 0;
}

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