Submission #911164

#	Time	Username	Problem	Language	Result	Execution time	Memory
911164		lighton	Bridges (APIO19_bridges)	C++17	14 / 100	92 ms	17376 KiB

bridges

#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
int N,M,Q;
pair<int, int> edge[100001];
pair<int, int> edgeidx[1000001];
vector<pair<int,int> > adj[100001];
int chk[100001];
int dfs(int now, int c){
    chk[now] = 1;
    int ret = 1;
    for(auto &[nxt,cost] : adj[now]){
        if(chk[nxt]) continue;
        if(cost < c) continue;
        ret += dfs(nxt,c);
    }
    return ret;
}
struct Query{
    int st, c, id;
    bool operator<(const Query &r) const{
        if(c==r.c) return id<r.id;
        return c<r.c;
    }
} q[100001];

struct DSU{
    int grp[100001];
    int sz[100001];
    void init(){
        forf(i,1,N){
            grp[i] = i;
            sz[i] = 1;
        }
    }
    int fi(int x){
        if(grp[x] == x) return x;
        return grp[x] = fi(grp[x]);
    }
    void un(int x, int y){
        x = fi(x); y = fi(y);
        sz[y] += sz[x]; sz[x] = 0;
        grp[x] = y;
    }
} dsu;
struct Event{
    int t;
    int q;
    int u,v;
    int id;
    bool operator<(const Event &r) const{
        if(t == r.t){
            if(q==r.q) return id<r.id;
            return q<r.q;
        }
        else return t>r.t;
    }
};
vector<Event> events;

int ans[100001];

int main(){
    scanf("%d %d" , &N,&M);
    forf(i,1,M){
        int u,v,c;
        scanf("%d %d %d" , &u,&v,&c);
        edge[i] = {u,v};
        edgeidx[i] = {adj[u].size(),adj[v].size()};
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
        events.push_back({c,0,u,v,i});
    }

    scanf("%d" , &Q);
    forf(i,1,Q){
        int cmd,a,b;
        scanf("%d %d %d" , &cmd,&a,&b);
        events.push_back({b,1,a,0,i});
    }
    sort(all(events));
    dsu.init();

    for(auto &i : events){

        if(i.q){
            ans[i.id] = dsu.sz[dsu.fi(i.u)];
        }
        else{
            if(dsu.fi(i.u) != dsu.fi(i.v)) dsu.un(i.u,i.v);
        }
    }

    forf(i,1,Q) printf("%d\n" , ans[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d %d" , &N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d %d %d" , &u,&v,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d" , &Q);
      |     ~~~~~^~~~~~~~~~~
bridges.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d %d %d" , &cmd,&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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