Submission #678678

#	Time	Username	Problem	Language	Result	Execution time	Memory
678678		qwerasdfzxcl	Bridges (APIO19_bridges)	C++17	43 / 100	3065 ms	5744 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;

struct Seg{
    int tree[100100], sz;
    void init(int n, int a[]){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
        for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
    }
    int query(int l, int r){
        ++r;
        int ret = 1e9;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
}tree;
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];}

void solve_subtask2(int n, int m, int q){
    tree.init(m+1, D);
    for (int i=1;i<=q;i++){
        if (op[i]==1) tree.update(qa[i], qb[i]);
        else{
            int L = qa[i], R = qa[i];

            int tl = 1, tr = qa[i] - 1;
            while(tl<=tr){
                int tm = (tl+tr)>>1;
                if (tree.query(tm, qa[i]-1) >= qb[i]) L = tm, tr = tm-1;
                else tl = tm+1;
            }

            tl = qa[i], tr = m;
            while(tl<=tr){
                int tm = (tl+tr)>>1;
                if (tree.query(qa[i], tm) >= qb[i]) R = tm+1, tl = tm+1;
                else tr = tm-1;
            }

            printf("%d\n", R-L+1);
        }
    }
    exit(0);
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> I;

    bool subtask2 = true;
    for (int i=1;i<=m;i++){
        scanf("%d %d %d", U+i, V+i, D+i);
        if (m!=n-1 || U[i]!=i || V[i]!=i+1) subtask2 = false;
        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);

    if (subtask2) solve_subtask2(n, m, q);

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

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