Submission #448719

#	Time	Username	Problem	Language	Result	Execution time	Memory
448719		JovanB	Bridges (APIO19_bridges)	C++17	100 / 100	2315 ms	111816 KiB

bridges

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

using ll = long long;
using ld = long double;

const int N = 50000;
const int M = 100000;
const int K = 600;

int ea[M+5];
int eb[M+5];
int ec[M+5];
bool changed[M+5];

int qt[M+5];
int qa[M+5];
int qb[M+5];

struct DSU{
    int n;
    int par[N+5];
    int sz[N+5];
    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }
    int root(int x){ return (x == par[x] ? x : par[x] = root(par[x])); }
    void povezi(int a, int b){
        a = root(a);
        b = root(b);
        if(a == b) return;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
    }
} dsu;

int sol[M+5];

const int INF = 1000000007;

vector <int> ima[M+5];
int gde[M+5];

vector <pair <int, int>> unerased;

vector <int> graf[N+5];

bool visited[N+5];

int dfs(int v){
    int svi = dsu.sz[v];
    visited[v] = 1;
    for(auto c : graf[v]) if(!visited[c]) svi += dfs(c);
    return svi;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        cin >> ea[i] >> eb[i] >> ec[i];
        unerased.push_back({ec[i], i});
    }
    int qrs;
    cin >> qrs;
    int qq = 0;
    sort(unerased.begin(), unerased.end());
    for(int ql=1; ql<=qrs; ql+=K){
        int qr = min(qrs, ql+K-1);
        dsu.init(n);
        vector <pair <int, pair <int, int>>> dvec;
        vector <int> ch;
        for(int i=ql; i<=qr; i++){
            cin >> qt[i] >> qa[i] >> qb[i];
            if(qt[i] == 1){
                if(!changed[qa[i]]){
                    ch.push_back(qa[i]);
                }
                changed[qa[i]] = 1;
            }
            else{
                qq++;
                gde[i] = qq;
                dvec.push_back({qb[i], {qq, qa[i]}});
            }
        }
        sort(dvec.begin(), dvec.end());
        vector <pair <int, pair <int, int>>> vec;
        int j = 0;
        for(auto c : unerased){
            while(j < dvec.size() && c.first >= dvec[j].first){
                vec.push_back(dvec[j]);
                j++;
            }
            if(!changed[c.second]) vec.push_back({c.first, {INF, c.second}});
        }
        while(j < dvec.size()){
            vec.push_back(dvec[j]);
            j++;
        }
        reverse(vec.begin(), vec.end());
        for(int i=ql; i<=qr; i++){
            if(qt[i] == 1) ec[qa[i]] = qb[i];
            else{
                for(auto c : ch){
                    if(ec[c] >= qb[i]) ima[gde[i]].push_back(c);
                }
            }
        }
        for(auto x : vec){
            if(x.second.first == INF) dsu.povezi(ea[x.second.second], eb[x.second.second]);
            else{
                int ind = x.second.first;
                int p = x.second.second;
                p = dsu.root(p);
                for(auto c : ima[ind]){
                    int a = dsu.root(ea[c]);
                    int b = dsu.root(eb[c]);
                    if(a == b) continue;
                    graf[a].push_back(b);
                    graf[b].push_back(a);
                }
                sol[ind] = dfs(p);
                visited[p] = 0;
                for(auto c : ima[ind]){
                    int a = dsu.root(ea[c]);
                    int b = dsu.root(eb[c]);
                    graf[a].clear();
                    graf[b].clear();
                    visited[a] = visited[b] = 0;
                }
            }
        }
        for(int i=ql; i<=qr; i++) if(gde[i]) ima[gde[i]].clear();
        vector <pair <int, int>> nv;
        vector <pair <int, int>> dv;
        for(auto c : ch){
            dv.push_back({ec[c], c});
        }
        sort(dv.begin(), dv.end());
        j = 0;
        for(auto c : unerased){
            while(j < dv.size() && c.first >= dv[j].first){
                nv.push_back(dv[j]);
                j++;
            }
            if(!changed[c.second]) nv.push_back(c);
        }
        while(j < dv.size()){
            nv.push_back(dv[j]);
            j++;
        }
        unerased = nv;
        nv.clear();
        nv.shrink_to_fit();
        for(auto c : ch) changed[c] = 0;
    }
    for(int i=1; i<=qq; i++) cout << sol[i] << "\n";
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             while(j < dvec.size() && c.first >= dvec[j].first){
      |                   ~~^~~~~~~~~~~~~
bridges.cpp:106:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while(j < dvec.size()){
      |               ~~^~~~~~~~~~~~~
bridges.cpp:152:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             while(j < dv.size() && c.first >= dv[j].first){
      |                   ~~^~~~~~~~~~~
bridges.cpp:158:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         while(j < dv.size()){
      |               ~~^~~~~~~~~~~

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