Submission #237321

#	Time	Username	Problem	Language	Result	Execution time	Memory
237321		jhnah917	Bridges (APIO19_bridges)	C++14	100 / 100	2459 ms	451944 KiB

bridges

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int sq = 1000;

struct Edge{
    int s, e, x, i;
    Edge(int s, int e, int x, int i) : s(s), e(e), x(x), i(i) {}
    Edge() : Edge(0, 0, 0, 0) {}
    bool operator < (const Edge &t) const {
        return x > t.x;
    }
};
struct Query{
    int op, a, b, i;
    Query(int op, int a, int b, int i) : op(op), a(a), b(b), i(i) {}
    Query() : Query(0, 0, 0, 0) {}
    bool operator < (const Query &t) const {
        return b > t.b;
    }
};

struct UF_Roll{
    int par[50505]{}, sz[50505]{};
    stack<int, vector<int>> stk;
    void init(int n){
        iota(par+1, par+n+1, 1);
        fill(sz+1, sz+n+1, 1);
        while(stk.size()) stk.pop();
    }
    int find(int v){ return v == par[v] ? v : /*par[v] =*/ find(par[v]); }
    void merge(int u, int v){
        u = find(u), v = find(v);
        if(u == v){ stk.push(0); return; }
        if(sz[u] > sz[v]) swap(u, v);
        par[u] = v; sz[v] += sz[u]; stk.push(u);
    }
    void rollback(){
        int t = stk.top(); stk.pop();
        if(t) sz[par[t]] -= sz[t], par[t] = t;
    }
} uf;

int n, m, q;
Edge edge[101010];
Query qry[101010];
int ans[101010];

vector<Edge> g[101010];

bool change_chk[101010];
void solve(int s, int e){
    vector<Edge> change, no;
    vector<Query> now;
    uf.init(n);
    memset(change_chk+1, 0, sizeof(change_chk[0]) * m);
    for(int i=s; i<=e; i++){
        if(qry[i].op == 1) change_chk[qry[i].a] = 1;
        else now.push_back(qry[i]);
    }
    for(int i=1; i<=m; i++){
        if(change_chk[i]) change.push_back(edge[i]);
        else no.push_back(edge[i]);
    }
    sort(all(no)); sort(all(now));
    for(int i=s; i<=e; i++){
        if(qry[i].op == 1) edge[qry[i].a].x = qry[i].b;
        else for(int j=0; j<change.size(); j++) if(qry[i].b <= edge[change[j].i].x) g[i].push_back(change[j]);
    }
    int j = 0;
    for(const Query &i : now){
        while(j < no.size() && i.b <= no[j].x) uf.merge(no[j].s, no[j].e), j++;
        for(const Edge &k : g[i.i]) uf.merge(k.s, k.e);
        ans[i.i] = uf.sz[uf.find(i.a)];
        for(int k=0; k<g[i.i].size(); k++) uf.rollback();
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=m; i++) cin >> edge[i].s >> edge[i].e >> edge[i].x, edge[i].i = i;
    cin >> q;
    for(int i=1; i<=q; i++) cin >> qry[i].op >> qry[i].a >> qry[i].b, qry[i].i = i;
    for(int i=1; ; i++){
        int s = sq * (i-1) + 1;
        int e = min(sq * i, q);
        solve(s, e);
        if(e == q) break;
    }
    for(int i=1; i<=q; i++) if(qry[i].op == 2) cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'void solve(int, int)':
bridges.cpp:69:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else for(int j=0; j<change.size(); j++) if(qry[i].b <= edge[change[j].i].x) g[i].push_back(change[j]);
                           ~^~~~~~~~~~~~~~
bridges.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < no.size() && i.b <= no[j].x) uf.merge(no[j].s, no[j].e), j++;
               ~~^~~~~~~~~~~
bridges.cpp:76:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k=0; k<g[i.i].size(); k++) uf.rollback();
                      ~^~~~~~~~~~~~~~

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