Submission #751078

#	Time	Username	Problem	Language	Result	Execution time	Memory
751078		Seb	Bridges (APIO19_bridges)	C++17	14 / 100	2612 ms	14120 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 = 600;

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

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;
    for (int i=l;i<=r;i++) {
        if (t[i]==2)  ask.push_back(i);
        else changed[x[i]] = true;
    }
    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];});
    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=l;j<ask[i];j++) if (t[j]==1) {
            if (y[j] >= y[ask[i]]) unir(u[x[j]],v[x[j]]);
            flag[x[j]] = true;
        }
        for (int j=l;j<=r;j++) if (t[j]==1 && flag[x[j]]==false && w[x[j]] >= y[ask[i]]) unir(u[x[j]],v[x[j]]);
        ans[ask[i]] = sz[padre(x[ask[i]])];
        rollback(aux);
        for (int j=l;j<ask[i];j++) if (t[j]==1) flag[x[j]] = false;
    }
    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:74:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     if (!ask.empty()) for (int i=0;i<ask.size();i++) {
      |                                    ~^~~~~~~~~~~
bridges.cpp:75:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         while (!unchanged.empty() && in<unchanged.size() && w[unchanged[in]] >= y[ask[i]]) {
      |                                      ~~^~~~~~~~~~~~~~~~~

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