Submission #678672

#	Time	Username	Problem	Language	Result	Execution time	Memory
678672		qwerasdfzxcl	Bridges (APIO19_bridges)	C++17	27 / 100	3074 ms	8172 KiB

bridges

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct DSU{
    int path[50050], sz[50050];
    void init(int n){for (int i=1;i<=n;i++) path[i] = i, sz[i] = 1;}
    int find(int s){
        if (s==path[s]) return s;
        return path[s] = find(path[s]);
    }
    void merge(int s, int v){
        s = find(s), v = find(v);
        if (s==v) return;
        path[s] = v;
        sz[v] += sz[s];
    }
    int size(int s){return sz[find(s)];}
}dsu;
int U[100100], V[100100], D[100100], op[100100], qa[100100], qb[100100], ans[100100];

bool cmp(int i, int j){return D[i] > D[j];}
bool cmp2(int i, int j){return qb[i] > qb[j];}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> I;
    for (int i=1;i<=m;i++){
        scanf("%d %d %d", U+i, V+i, D+i);
        I.push_back(i);
    }

    int q;
    scanf("%d", &q);
    for (int i=1;i<=q;i++) scanf("%d %d %d", op+i, qa+i, qb+i);

    for (int i=1;i<=q;){
        int r = i;
        while(r<=q && op[r]==2) ++r;

        dsu.init(n);
        sort(I.begin(), I.end(), cmp);

        vector<int> qI;
        for (int j=i;j<r;j++) qI.push_back(j);
        sort(qI.begin(), qI.end(), cmp2);

        int pt = 0;
        for (int j:qI){
            while(pt<(int)I.size() && D[I[pt]] >= qb[j]){
                dsu.merge(U[I[pt]], V[I[pt]]);
                ++pt;
            }
            ans[j] = dsu.size(qa[j]);
        }

        if (r<=q){
            D[qa[r]] = qb[r];
        }

        i = r+1;
    }

    for (int i=1;i<=q;i++) if (op[i]==2) printf("%d\n", ans[i]);
    return 0;
}

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:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d %d %d", U+i, V+i, D+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:36:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     for (int i=1;i<=q;i++) scanf("%d %d %d", op+i, qa+i, qb+i);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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