Submission #335050

#	Time	Username	Problem	Language	Result	Execution time	Memory
335050		TheEpicCowOfLife	Bridges (APIO19_bridges)	C++14	14 / 100	174 ms	20068 KiB

bridges

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

int n,m;

struct e{
    int a,b,w;
};
vector<e> ev;

int ua[100005];
int ncnt;
int height[100005];
int sz[100005];

int f(int x){
    if (ua[x] == x) return x;
    return ua[x] = f(ua[x]);
}
int cur_node[100005]; // cur_node[i] is the node that represents the group led by node i
int par[100005][20];

int main(){
    scanf("%d %d", &n, &m);
    height[0] = -1;
    ncnt = n;
    for (int i = 1; i <= n; i++){
        ua[i] = i;
        sz[i] = 1;
        height[i] = 2e9;
        cur_node[i] = i;
    }
    for (int i = 1; i <= m; i++){
        int a,b,w;
        scanf("%d %d %d", &a, &b, &w);
        ev.push_back({a,b,w});
    }
    sort(ev.begin(),ev.end(),[](e l, e r){
        return l.w > r.w;
    });

    for (e cur : ev){
        int a = cur.a;
        int b = cur.b;
        if (f(a) == f(b)) continue;
        int w = cur.w;
        int fa = cur_node[f(a)];
        int fb = cur_node[f(b)];
        int cn = ++ncnt; // cn is the new node we're making
        height[cn] = w;
        par[fa][0] = cn;
        par[fb][0] = cn;     
        sz[cn] = sz[fa] + sz[fb];
        ua[f(a)] = f(b);
        cur_node[f(b)] = cn;     
        // printf("merging (%d %d) %d %d\n", fa,fb, sz[cn],height[cn]);
    }


    for (int i = 1; i <= 18; i++){
        for (int j = 1; j <= ncnt; j++){
            par[j][i] = par[par[j][i-1]][i-1];
        }
    }
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++){
        int t,x,w;
        scanf("%d %d %d", &t, &x, &w);
        assert(t == 2);
        for (int i = 18; i >= 0; i--){
            if (height[par[x][i]] >= w){
                x = par[x][i];
            }
        }
        // printf("%d\n", x);
        printf("%d\n", sz[x]);
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |         scanf("%d %d %d", &a, &b, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |         scanf("%d %d %d", &t, &x, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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