Submission #1366847

#TimeUsernameProblemLanguageResultExecution timeMemory
1366847hmms127Bridges (APIO19_bridges)C++20
0 / 100
45 ms9308 KiB
#include "bits/stdc++.h"
using namespace std;
#define f1(n) for(int i=0;i<n;i++)
#define f2(m,n,q) for(int i=m;i<n;i+=q)
#define int long long
#define pb push_back
constexpr int N=1e5+5,inf=1e18;
using pr=pair<int,int>;
using ar=array<int,3>;
struct DSU {
    vector<int>par,sz;
    DSU(int n) {
        par.resize(n+1);sz.resize(n+1,1);
        f2(1,n+1,1)par[i]=i,sz[i]=1;
    }
    int root(int u){return (par[u]==u ? u:par[u]=root(par[u]));}
    bool merge(int u,int v) {
        int ru=root(u),rv=root(v);
        if (ru==rv)return 0;
        if (sz[ru]>sz[rv])swap(ru,rv);
        par[ru]=rv;sz[rv]+=sz[ru];
        return 1;
    }
};
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,m;cin>>n>>m;
    vector<ar>edg;
    f1(m) {
        int u,v,d;cin>>u>>v>>d;
        edg.pb({d,u,v});
    }
    sort(edg.rbegin(),edg.rend());
    int q;cin>>q;
    vector<ar>qu(q);
    f1(q) {
        int t,x,y;cin>>t>>x>>y;
        qu.pb({y,x,i});
    }
    sort(qu.rbegin(),qu.rend());
    int ans[q];int r=0;DSU d(n);
    for (auto it:qu) {
        while (r<m&&edg[r][0]>=it[0])d.merge(edg[r][1],edg[r++][2]);
        ans[it[2]]=d.sz[d.root(it[1])];
    }
    f1(q)cout<<ans[i]<<'\n';

}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...