Submission #784251

#	Time	Username	Problem	Language	Result	Execution time	Memory
784251		Seb	Bridges (APIO19_bridges)	C++17	100 / 100	2574 ms	14036 KiB

bridges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

#define f first
#define s second

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

ll u[MAXN],v[MAXN],d[MAXN],t[MAXN],s[MAXN],w[MAXN],pa[MAXN],ans[MAXN],sz[MAXN],sus[MAXN];
priority_queue <pair<ll,ll>> pq,pq2;
vector <ll> roll,vec;
bool vis[MAXN];

ll padre(ll a) {
    if (sz[a] == 0) {
        sz[a] = 1;
        pa[a] = a;
    }
    if (pa[a] == a) return a;
    return padre(pa[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];
    pa[b] = a;
    roll.push_back(b);
    return;
}

void rollback(ll pausa) {
    while (roll.size() != pausa) {
        ll aux = roll.back();
        roll.pop_back();
        sz[pa[aux]] -= sz[aux];
        pa[aux] = aux;
    }
    return;
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
roll.push_back(0);
ll n,m,q;
cin>>n>>m;
for (int i=0;i<m;i++) cin>>u[i]>>v[i]>>d[i];
cin>>q;
for (int i=0;i<q;i++) cin>>t[i]>>s[i]>>w[i];
for (int l=0;l<q;l+=sq) {
    int r = min(l+sq-1,q-1);
    for (int i=l;i<=r;i++) {
        if (t[i]==2) pq2.push({w[i],i});
        else {
            vis[s[i]-1] = true;
            vec.push_back(s[i]-1);
        }
    }
    for (int i=0;i<m;i++) if (vis[i] == false) pq.push({d[i],i});
    while (!pq2.empty()) {
        pair<ll,ll> p = pq2.top();
        pq2.pop();
        while (!pq.empty() && pq.top().f >= p.f) {
            unir(u[pq.top().s],v[pq.top().s]);
            pq.pop();
        }
        int pau = roll.size();
        for (int i=l;i<=p.s;i++) if (t[i]==1) {
            sus[s[i]-1] = w[i];
        }
        for (int i=0;i<vec.size();i++) {
            if (sus[vec[i]]==0) {
                if (d[vec[i]] >= p.f) unir(u[vec[i]],v[vec[i]]);
            }
            else {
                if (sus[vec[i]] >= p.f) unir(u[vec[i]],v[vec[i]]);
            }
        }
        for (int i=l;i<=p.s;i++) if (t[i]==1) sus[s[i]-1] = 0;
        ans[p.s] = sz[padre(s[p.s])];
        rollback(pau);
    }
    for (int i=l;i<=r;i++) if (t[i]==1) d[s[i]-1] = w[i];
    while (!pq.empty()) pq.pop();
    while (!pq2.empty()) pq2.pop();
    rollback(1);
    for (int i=0;i<m;i++) {
        vis[i] = false;
        sus[i] = 0;
    }
    vec.clear();
}
for (int i=0;i<q;i++) if (ans[i]!=0) cout<<ans[i]<<"\n";
return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(ll)':
bridges.cpp:42:24: 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]
   42 |     while (roll.size() != pausa) {
      |            ~~~~~~~~~~~~^~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:80:23: 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 i=0;i<vec.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