Submission #1317875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317875		nmduck6	Bridges (APIO19_bridges)	C++20	100 / 100	3000 ms	5552 KiB

bridges

#include <iostream>
#include <iomanip>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

#define _F ""
// #define MULTITEST

using namespace std;

struct edge_t {
    int u, v, w;
};

struct query_t {
    int ind, t, arg1, arg2;
};

#define MAXN 50000
#define MAXM 100000
#define MAXQ 100000
#define BS 256

// chia thanh block kthuoc B
// for moi block, sweepline truy van 2 tu tren xuong, them moi canh o ben trai block co w >= thg do (tong O(mqlogn/B)),
// roi them cac canh truoc thg do co trong so >= w; xong roi thi rollback cac canh nay (O(Blogn) cho tung truy van)
// -> O(mqlogn/B + qBlogn)

int n, m, q;
edge_t edges[MAXM + 1];
int sortedges[MAXM + 1];
query_t queries[MAXQ + 1];
int label[MAXN + 1];
vector<pair<int, int>> updates;
int ret[MAXQ + 1];

int findset(int u) {
    return label[u] < 0 ? u : findset(label[u]);
}

void unite(int u, int v) {
    int r = findset(u), s = findset(v);
    if (r == s) return;
    if (-label[r] < -label[s]) swap(r, s);
    updates.emplace_back(r, label[r]);
    updates.emplace_back(s, label[s]);
    label[r] += label[s];
    label[s] = r;
}

int snapshot() {
    return updates.size();
}

void rollback(int snap) {
    while ((int)updates.size() != snap) {
        auto [r, labelr] = updates.back();
        label[r] = labelr;
        updates.pop_back();
    }
}

void cleardsf() {
    fill(label + 1, label + n + 1, -1);
    updates.clear();
}

inline int getblock(int ind) {
    return (ind - 1) / BS;
}

inline int getleft(int block) {
    return block * BS + 1;
}

void pre() {
    cin >> n >> m;
    cleardsf();
    iota(sortedges + 1, sortedges + m + 1, 1);
    for (int i = 1; i <= m; i++) cin >> edges[i].u >> edges[i].v >> edges[i].w;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        queries[i].ind = i;
        cin >> queries[i].t >> queries[i].arg1 >> queries[i].arg2;
    }
}

bool updlater[MAXM + 1];
bool seen[MAXM + 1];

void run() {
    vector<int> query1, query2, updlaterv;
    for (int i = getblock(1); i <= getblock(q); i++) {
        query1.clear();
        query2.clear();
        updlaterv.clear();
        cleardsf();
        for (int j = getleft(i); j <= min(q, getleft(i + 1) - 1); j++) {
            if (queries[j].t == 1) {
                updlater[queries[j].arg1] = true;
                updlaterv.emplace_back(queries[j].arg1);
                query1.emplace_back(j);
            } else query2.emplace_back(j);
        }
        sort(query2.begin(), query2.end(), [](const int first, const int second) {
            return queries[first].arg2 > queries[second].arg2;
        });
        sort(sortedges + 1, sortedges + m + 1, [](const int first, const int second) {
            return edges[first].w < edges[second].w;
        });
        int curm = m;
        vector<int> seenv;
        for (int query: query2) {
            seenv.clear();
            int qind = queries[query].ind, u = queries[query].arg1, w = queries[query].arg2;
            while (curm >= 1 && edges[sortedges[curm]].w >= w) {
                if (!updlater[sortedges[curm]]) unite(edges[sortedges[curm]].u, edges[sortedges[curm]].v);
                curm--;
            }
            int snap = snapshot();
            int endj = (int)(upper_bound(query1.begin(), query1.end(), query) - query1.begin()) - 1;
            for (int ind = endj; ind >= 0; ind--) {
                int j = query1[ind];
                if (!seen[queries[j].arg1]) {
                    seen[queries[j].arg1] = true;
                    seenv.emplace_back(queries[j].arg1);
                    if (queries[j].arg2 >= w) unite(edges[queries[j].arg1].u, edges[queries[j].arg1].v);
                }
            }
            for (int j: updlaterv) {
                if (!seen[j] && edges[j].w >= w) unite(edges[j].u, edges[j].v);
            }
            ret[qind] = -label[findset(u)];
            rollback(snap);
            for (int v: seenv) seen[v] = false;
        }
        for (int j: query1) {
            updlater[queries[j].arg1] = false;
            edges[queries[j].arg1].w = queries[j].arg2;
        }
    }
    for (int i = 1; i <= q; i++) if (ret[i]) cout << ret[i] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(_F".inp", "r")) {
        freopen(_F".inp", "r", stdin);
        freopen(_F".out", "w", stdout);
    }
    pre();
    int t = 1;
    #ifdef MULTITEST
    cin >> t;
    #endif
    while (t--) {
        run();
    }
}

/*
                                      #++*                                                          
                                  *-----::--+%                                                      
                                *---::---::--=------------=+##       %%%#                           
                               +-:::::-===-------::::::::::::::=*+-:--::::-+%                       
                             +-::::-=:::::::::::::::::::::--=-::::==:::::::::-*                     
               *#           #=::---::::::::::::::::::::::::::::--:::------:::::=*                   
             ##**          #=:--:::::::::::::::::::::::::::::::::--::::=-::-::::+                   
             #             +:--:::::::::::-::::::::::::::::::::::::--:::--:::-:::*                  
               *          *-+:::::::::::-:::::::::::::::--:::::::::::-:::--:::::::*                 
             **          #==::::::::::--::::::::::::::::::-:::::::::::-::--=:::-::=                 
              *  *       *+::::::::::-:::::::::::::::::::::-:::::::::::--::-=:::-:-+                
            **#          *-:::::::::-:::::::::::::::::::::-:::::::::::::--:::=:::-:-#               
                        *=:::::::::-::::::::::::::::::::::::-::::::::::::-::---:::--*               
                ***     +:::::::::-:::::::::::==:::::::::::::=::::::::::::-:--=::::-+               
                 *     *-::::::::--::::::::::-::--::::::::::::-:::::::::::---:--:::-=               
                       +:::::::::=:::::-:::-::::::-:-::::::::-=::::::::::::--:-=-:::=               
                      *-::::::::--:::-:::--::::::::=:-::::::::=-:::::::::::=-:-=-:::=               
                      +:::::::::=::-:::--::::::::::::=-:::::::-=::::::::::::=:==--::=               
         *====+**    #=:::::::::=-:--=--::-:::::::::::---::::::-::::::::::::=-==--::=               
         *-:::::::--:--:-::::::===-:-::::-::::::::::-:::-==-:::--:::::::::::+-==--::=               
          =-:----------:-::::::-::::::::::::::::::::::--:--:-===-:-:::::::::+==----:=               
            =-:----::--:-::::::-:::::::::::::::::::::::::::::::--:-:::::::::+:::::-==++*##          
              *-:--::----::::::-:::::::::::::::::::::::::::::::--:-:::::::::=--------:::::::-*      
                +-------=::::::-::=####*=::::::::::::::::::::::-::::::::::::-:----------::-=*       
                   +==--*::::::=:::::::::::::::::::::=###*+-:::=:-:::::::-:=---------::--=          
                      +-*=:::::-::::::::::::::::::::::::::=*-::-::::::::-+:=---:--::=+              
                      *:*+-:::::=:::::::::::::::::::::::::::::=:::::::::+-==-::-=+=-=               
                       *=++-::---=:::::::::::::::::::::::::::=:--:::::-+=-=-=+=====-=+              
                       ++*=*=::-===:::::::::::::::::::::::::---=-::::=++=+======------+             
                       =+=+*-=+=-==:::::::::::::::::::::::-==*=-:::-+++=--------=+==+++*            
                      #-*=*+----==++::::::::::-=:::::::::::-==-::=+*=------------=-----=+           
                      *+==*=--------=+=-:::::--======++++--=====----=------------==----=+           
                      +=-------------===+=--------------==-----------=------------=-----=*          
                     *=------------==--------------------=-----------=====--------=-----=+          
                    *=-------------==---------------------=----------=+====-------==+**++*          
                    *=-------------==----------------------=---------=====--------==---==+          
                    *=-------------==--------------------=++----------==----------=======+          
                    #+=------------==------------------=+==-----------=----------==-=====+          
                    +====-----------=----------------=+=====----------=---------=========*          
                    +--:+*+---------+----------------*====-==---------+==------==+=+*+==*           
                   *:-::++=-+==-----=+---------------===---==-----==+*#**=-=+==+++===+              
                   +:-::++-::::-=====+=--------------------==-==++++++++::--::::-+++=+              
                  #::-::++-::::::::::+#------------------=++++=--::-++=::-:::::::-+-=#              
                  *::-::++-::::::::-++*+---------------=++--::::::=++=::-:::::::::-+-*              
                 #-::-::++-:::::::-+++:-=------------=++--:::::::=++=::=:::::::::::==+              
                 *:::--:++=::::::=++-::=+=---------=++--::::::::-+++::-::::::::::::==+              
                 +:::-::=+=::::-+++-::---==-----=++**-:::::::::-+++::-:::::::::::::-==#             
                 =::::-:-++-::-+++::--::::::----*:-++=:::::::::+++::--::::::::::::::=-*             
                #-::::=::++-:-++=::-:::::::::::::::=++-:::::::+++-::-:::::::::::::::+-+             
                *-::::-::=+==++-::-::::::::::::::-::++=::::::=++=::=::::::::::::::::==-*            
                *-:::::-:-++++=::-::::::::::::::::-::++=::::-++=::=:::::::::::::::::-=-+            
                   ::::::-+++=:::::::::::::::::::::::=++-:::=++-:::::::::::::::::::::--             
*/

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(_F".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(_F".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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