Submission #911159

#	Time	Username	Problem	Language	Result	Execution time	Memory
911159		lighton	Bridges (APIO19_bridges)	C++17	13 / 100	3072 ms	13580 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];
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});
    }

    scanf("%d" , &Q);

    while(Q--){
        int cmd,a,b;
        scanf("%d %d %d" , &cmd,&a,&b);
        if(cmd==1){
            adj[edge[a].first][edgeidx[a].first].second = b;
            adj[edge[a].second][edgeidx[a].second].second = b;
        }
        else{
            forf(i,1,N) chk[i] = 0;
            printf("%d\n", dfs(a,b));
        }
    }
}

Compilation message (stderr)

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

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