Submission #922909

#	Time	Username	Problem	Language	Result	Execution time	Memory
922909		thangdz2k7	Bridges (APIO19_bridges)	C++17	100 / 100	1806 ms	33704 KiB

bridges

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e5 + 5;
const int blsize = 1000;

int n, m, q;
int u[N], v[N], d[N];
int t[N], b[N], w[N];
int par[N], ans[N], sz[N];

vector <int> adj[N];

int find(int u){
    if (u == par[u]) return u;
    return par[u] = find(par[u]);
}

void joint(int u, int v){
    u = find(u);
    v = find(v);
    if (u != v) {
        par[u] = v;
        sz[v] += sz[u];
    }
}

int cur[blsize + 5][blsize + 5];
bool to[N];

void dfs(int u, int &ans){
    if (to[u]) return;
    to[u] = 1;
    ans += sz[u];
    for (int v : adj[u]) if (!to[v]) dfs(v, ans);
}

void solve(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i){
        cin >> u[i] >> v[i] >> d[i];
    }

    cin >> q;

    for (int ed = 0; ed < q; ++ ed){
        cin >> t[ed] >> b[ed] >> w[ed];
        if (ed % blsize != blsize - 1 && ed != q - 1) continue;
        int st = (ed / blsize) * blsize;

        vector <int> ask;
        vector <bool> used(m + 5);
        for (int i = st; i <= ed; ++ i){
            if (t[i] & 1) used[b[i]] = 1;
            else ask.pb(i);
        }
        sort(ask.begin(), ask.end(), [&](int u, int v){
            return w[u] > w[v];
        });

        vector <int> keep;
        vector <int> chage;
        vector <int> pos(m + 5);
        for (int i = 1; i <= m; ++ i){
            if (used[i]) chage.pb(i);
            else keep.pb(i);
        }
        int nch = chage.size();
        for (int i = 0; i < chage.size(); ++ i) pos[chage[i]] = i;

        for (int time = 0; time <= ed - st; ++ time){
            for (int i = 0; i < nch; ++ i){
                if (time == 0) cur[i][time] = d[chage[i]];
                else cur[i][time] = cur[i][time - 1];
            }
            if (t[st + time] & 1){
                int idx = pos[b[st + time]];
                cur[idx][time] = w[st + time];
            }
        }

        sort(keep.begin(), keep.end(), [&](int u, int v){
            return d[u] > d[v];
        });

        for (int i = 1; i <= n; ++ i) par[i] = i, sz[i] = 1;
        int l = 0;
        for (int idx : ask){
            //cout << idx << endl;
            while (l < keep.size() && d[keep[l]] >= w[idx]){
                joint(u[keep[l]], v[keep[l]]);
                ++ l;
            }

            for (int i = 0; i < chage.size(); ++ i){
                if (cur[i][idx - st] >= w[idx]){
                    int U = find(u[chage[i]]);
                    int V = find(v[chage[i]]);
                    adj[U].pb(V);
                    adj[V].pb(U);
                    to[U] = 0;
                    to[V] = 0;
                }
            }
            to[find(b[idx])] = 0;

            //if (idx == 4) cout << sz[find(b[idx])] << endl;

            dfs(find(b[idx]), ans[idx]);

            for (int i = 0; i < chage.size(); ++ i){
                if (cur[i][idx - st] >= w[idx]){
                    int U = find(u[chage[i]]);
                    int V = find(v[chage[i]]);
                    adj[U].clear();
                    adj[V].clear();
                }
            }
        }

        for (int i = 0; i < chage.size(); ++ i){
            d[chage[i]] = cur[i][ed - st];
        }

    }

    for (int i = 0; i < q; ++ i) if (!(t[i] & 1)) cout << ans[i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < chage.size(); ++ i) pos[chage[i]] = i;
      |                         ~~^~~~~~~~~~~~~~
bridges.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             while (l < keep.size() && d[keep[l]] >= w[idx]){
      |                    ~~^~~~~~~~~~~~~
bridges.cpp:97:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for (int i = 0; i < chage.size(); ++ i){
      |                             ~~^~~~~~~~~~~~~~
bridges.cpp:113:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for (int i = 0; i < chage.size(); ++ i){
      |                             ~~^~~~~~~~~~~~~~
bridges.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int i = 0; i < chage.size(); ++ i){
      |                         ~~^~~~~~~~~~~~~~

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