Submission #672725

#	Time	Username	Problem	Language	Result	Execution time	Memory
672725		jhnah917	Bridges (APIO19_bridges)	C++14	100 / 100	2222 ms	348300 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
constexpr int B = 1000;

struct Edge{ int u, v, w; };
struct Query{ int op, a, b, idx; };

struct UnionFind{
    vector<int> p, s;
    stack<pair<int,int>> stk;
    UnionFind(int n) : p(n+1), s(n+1), stk() {
        iota(p.begin(), p.end(), 0);
        fill(s.begin(), s.end(), 1);
    }
    int find(int v){ return v == p[v] ? v : find(p[v]); }
    void merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v){ stk.emplace(-1, -1); return; }
        if(s[u] > s[v]) swap(u, v);
        p[u] = v; s[v] += s[u];
        stk.emplace(u, v);
    }
    void undo(){
        auto [u,v] = stk.top(); stk.pop();
        if(u != -1) p[u] = u, s[v] -= s[u];
    }
    int size(int v){ return s[find(v)]; }
};

int N, M, Q, R[101010], C[101010];
Edge E[101010];
Query Qry[101010];
vector<Edge> G[101010];

void Solve(int l, int r){
    memset(C, 0, sizeof C);
    vector<int> dy, st; // dynamic/static edge
    vector<Query> ask; // query
    for(int i=l; i<=r; i++){
        if(Qry[i].op == 1) C[Qry[i].a] = 1;
        else ask.push_back(Qry[i]);
    }
    for(int i=1; i<=M; i++) (C[i] ? dy : st).push_back(i);
    for(int i=l; i<=r; i++){
        if(Qry[i].op == 1) E[Qry[i].a].w = Qry[i].b;
        else for(auto j : dy) if(Qry[i].b <= E[j].w) G[i].push_back(E[j]);
    }

    sort(ask.begin(), ask.end(), [](auto q1, auto q2){ return q1.b > q2.b; });
    sort(st.begin(), st.end(), [](auto e1, auto e2){ return E[e1].w > E[e2].w; });

    UnionFind U(N);
    for(int i=0, j=0; i<ask.size(); i++){
        while(j < st.size() && ask[i].b <= E[st[j]].w) U.merge(E[st[j]].u, E[st[j]].v), j++;
        for(const auto &[u,v,w] : G[ask[i].idx]) U.merge(u, v);
        R[ask[i].idx] = U.size(ask[i].a);
        for(const auto &[u,v,w] : G[ask[i].idx]) U.undo();
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++) cin >> E[i].u >> E[i].v >> E[i].w;
    cin >> Q;
    for(int i=1; i<=Q; i++) cin >> Qry[i].op >> Qry[i].a >> Qry[i].b, Qry[i].idx = i;
    for(int i=1; i<=Q; i+=B) Solve(i, min(Q, i+B-1));
    for(int i=1; i<=Q; i++) if(Qry[i].op == 2) cout << R[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In member function 'void UnionFind::undo()':
bridges.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         auto [u,v] = stk.top(); stk.pop();
      |              ^
bridges.cpp: In function 'void Solve(int, int)':
bridges.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0, j=0; i<ask.size(); i++){
      |                       ~^~~~~~~~~~~
bridges.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while(j < st.size() && ask[i].b <= E[st[j]].w) U.merge(E[st[j]].u, E[st[j]].v), j++;
      |               ~~^~~~~~~~~~~
bridges.cpp:55:25: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         for(const auto &[u,v,w] : G[ask[i].idx]) U.merge(u, v);
      |                         ^
bridges.cpp:57:25: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for(const auto &[u,v,w] : G[ask[i].idx]) U.undo();
      |                         ^
bridges.cpp:57:25: warning: unused structured binding declaration [-Wunused-variable]
   57 |         for(const auto &[u,v,w] : G[ask[i].idx]) U.undo();
      |                         ^~~~~~~

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