Submission #751125

#	Time	Username	Problem	Language	Result	Execution time	Memory
751125		Seb	Bridges (APIO19_bridges)	C++17	100 / 100	2750 ms	20928 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first
#define s second

const ll MAXN = 1e5+5;
const ll sq = 1000;

ll sz[MAXN],p[MAXN],u[MAXN],v[MAXN],w[MAXN],t[MAXN],x[MAXN],y[MAXN],ans[MAXN];
bool changed[MAXN];
vector <ll> sk,join[sq+5];

ll padre(ll a) {
    if (sz[a]==0) {
        sz[a] = 1;
        p[a] = a;
    }
    if (p[a]==a) return a;
    return padre(p[a]);
}

void unir(ll a, ll b) {
    a = padre(a);
    b = padre(b);
    if (a==b) return;
    if (sz[a]<sz[b]) swap(a,b);
    sz[a] += sz[b];
    p[b] = a;
    sk.push_back(b);
    return;
}

void rollback(ll k) {
    while (!sk.empty() && sk.size()>k) {
        ll a = sk.back();
        sk.pop_back();
        sz[p[a]] -= sz[a];
        p[a] = a;
    }
    return;
}

void limpia() {
    for (int i=0;i<MAXN;i++) {
        p[i] = sz[i] = 0;
        changed[i] = false;
    }
    sk.clear();
    return;
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,m,q;
cin>>n>>m;
for (int i=1;i<=m;i++) cin>>u[i]>>v[i]>>w[i];
cin>>q;
for (int i=1;i<=q;i++) cin>>t[i]>>x[i]>>y[i];
for (int l=1;l<=q;l+=sq) {
    int r = min(l+sq-1,q);
    vector <ll> ask,unchanged,upd;
    for (int i=l;i<=r;i++) {
        if (t[i]==2) ask.push_back(i);
        else {
            changed[x[i]] = true;
            upd.push_back(i);
        }
    }
    for (int i=1;i<=m;i++) if (!changed[i]) unchanged.push_back(i);
    sort(ask.begin(),ask.end(),[&](ll a, ll b) {return y[a] > y[b];});
    sort(unchanged.begin(),unchanged.end(),[&](ll a, ll b) {return w[a] > w[b];});
    for (int i=l;i<=r;i++) {
        if (t[i]==1) w[x[i]] = y[i];
        else {
            join[i-l].clear();
            for (int j=0;j<upd.size();j++) if (w[x[upd[j]]] >= y[i]) join[i-l].push_back(x[upd[j]]);
        }
    }
    int in=0;
    if (!ask.empty()) for (int i=0;i<ask.size();i++) {
        while (!unchanged.empty() && in<unchanged.size() && w[unchanged[in]] >= y[ask[i]]) {
            unir(u[unchanged[in]],v[unchanged[in]]);
            in++;
        }
        int aux;
        if (!sk.empty()) aux = sk.size();
        else aux = 0;
        for (int j=0;j<join[ask[i]-l].size();j++) unir(u[join[ask[i]-l][j]],v[join[ask[i]-l][j]]);
        ans[ask[i]] = sz[padre(x[ask[i]])];
        rollback(aux);
    }
    for (int i=l;i<=r;i++) if (t[i]==1) w[x[i]] = y[i];
    limpia();
}
for (int i=1;i<=q;i++) if (t[i]==2) cout<<ans[i]<<'\n';
return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(ll)':
bridges.cpp:38:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   38 |     while (!sk.empty() && sk.size()>k) {
      |                           ~~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for (int j=0;j<upd.size();j++) if (w[x[upd[j]]] >= y[i]) join[i-l].push_back(x[upd[j]]);
      |                          ~^~~~~~~~~~~
bridges.cpp:84:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if (!ask.empty()) for (int i=0;i<ask.size();i++) {
      |                                    ~^~~~~~~~~~~
bridges.cpp:85:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         while (!unchanged.empty() && in<unchanged.size() && w[unchanged[in]] >= y[ask[i]]) {
      |                                      ~~^~~~~~~~~~~~~~~~~
bridges.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int j=0;j<join[ask[i]-l].size();j++) unir(u[join[ask[i]-l][j]],v[join[ask[i]-l][j]]);
      |                      ~^~~~~~~~~~~~~~~~~~~~~~

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