Submission #967207

#	Time	Username	Problem	Language	Result	Execution time	Memory
967207		socpite	Bridges (APIO19_bridges)	C++14	100 / 100	2619 ms	24052 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
const int blsz = 350;

int n, m, q;

int U[maxn], V[maxn], W[maxn];

int Wnew[maxn];

int T[maxn], id[maxn], val[maxn], ans[maxn];
bool chk[maxn];

int up[maxn], vis[maxn];

vector<int> g[maxn];

int dfs(int x, int pos){
    int res = -up[x];
    vis[x] = pos;
    for(auto v: g[x]){
        if(vis[v] == pos)continue;
        res += dfs(v, pos);
    }
    return res;
}

int Find(int x){
    return up[x] < 0 ? x : up[x] = Find(up[x]);
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a == b)return;
    up[a] += up[b];
    up[b] = a;
}

struct cmp{
    bool operator()(const int &a, const int &b)const {
        return make_pair(W[a], a) > make_pair(W[b], b);
    }
};

void solve_query(int l, int pos, vector<int> &changed){
    for(auto v: changed)Wnew[v] = W[v];
    for(int i = l; i < pos; i++){
        if(T[i] == 1)Wnew[id[i]] = val[i];
    }
    for(auto v: changed)if(Wnew[v] >= val[pos]){
        g[Find(U[v])].push_back(Find(V[v]));
        g[Find(V[v])].push_back(Find(U[v]));
    }
    ans[pos] = dfs(Find(id[pos]), pos);
    for(auto v: changed){
        g[Find(U[v])].clear();
        g[Find(V[v])].clear();
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)vis[i] = -1;
    set<int, cmp> st;
    for(int i = 1; i <= m; i++){
        cin >> U[i] >> V[i] >> W[i];
        st.insert(i);
    }
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> T[i] >> id[i] >> val[i];
    }
    for(int l = 0; l < q; l += blsz){
        int r = min(l + blsz, q);

        // solving queries

        vector<int> changed;
        vector<pair<int, int>> queries;
        for(int i = l; i < r; i++){
            if(T[i] == 1){
                changed.push_back(id[i]);
                chk[id[i]] = 1;
            }
            else queries.push_back({val[i], i});
        }
        sort(queries.begin(), queries.end());
        reverse(queries.begin(), queries.end());

        int ptr = 0;
        for(int i = 1; i <= n; i++)up[i] = -1;
        for(auto v: st){
            while(ptr < queries.size() && queries[ptr].first > W[v])solve_query(l, queries[ptr++].second, changed);
            if(!chk[v])Union(U[v], V[v]);
        }
        while(ptr < queries.size())solve_query(l, queries[ptr++].second, changed);

        // update and reset. also prints answers

        for(int i = l; i < r; i++){
            if(T[i] == 1){
                chk[id[i]] = 0;

                st.erase(id[i]);
                W[id[i]] = val[i];
                st.insert(id[i]);
            }
            else cout << ans[i] << "\n";
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             while(ptr < queries.size() && queries[ptr].first > W[v])solve_query(l, queries[ptr++].second, changed);
      |                   ~~~~^~~~~~~~~~~~~~~~
bridges.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         while(ptr < queries.size())solve_query(l, queries[ptr++].second, changed);
      |               ~~~~^~~~~~~~~~~~~~~~

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