Submission #673766

#	Time	Username	Problem	Language	Result	Execution time	Memory
673766		Cookie	Bridges (APIO19_bridges)	C++14	59 / 100	3027 ms	8364 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

 #pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//sorry for pragma :()
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#include<fstream>
ifstream fin("ss.inp");
ofstream fout("ss.out");
#define pii pair<int, int>
#define pll pair<ll, ll>

const ll mod = 1e9 + 7, mod2 = 1e9 + 9;
const int mxn = 5e4, mxq = 1e5, sq = 450, mxm = 1e5;
int n, m, q;
struct DSU{
    vt<pii>past_sz, past_p;
    int p[mxn + 1], sz[mxn + 1];
    void init(){
        for(int i = 1; i <= n; i++){
            p[i] = i; sz[i] = 1;
        }
        past_sz.clear(); past_p.clear();
    }
    int fp(int a){
        if(p[a] == a)return(a);
        return(fp(p[a]));
    }
    int getsz(int p){
        return(sz[fp(p)]);
    }
    void unon(int u, int v){
        u = fp(u); v = fp(v);
        if(sz[u] < sz[v])swap(u, v);
        past_sz.pb({u, sz[u]}); past_p.pb({v, p[v]});
        if(u != v){
            sz[u] += sz[v]; p[v] = u;
        }
    }
    void rollback(){
        p[past_p.back().fi] = past_p.back().se; past_p.pop_back();
        sz[past_sz.back().fi] = past_sz.back().se; past_sz.pop_back();
    }
    
};
struct e{
    int u, v, w;
    bool operator <(const e &b){
        return(w > b.w);
    }
};
struct qq{
    int id, a, b;
};
struct qq2{
    int s, w, id;
    bool operator <(const qq2 &b){
        return(w > b.w);
    }
};
vt<e>edge;

DSU dsu;
vt<qq>queries[sq + 1];
bool change[mxm + 1];
int nww[mxm + 1], ans[mxn + 1];
void solve(vt<qq>v){
    dsu.init();
    vt<qq2>ask; vt<int>idd;
    for(int i = 0; i < v.size(); i++){
        if(v[i].id == 1){
            change[v[i].a] = true; idd.pb(i);
        }
        else ask.pb({v[i].a, v[i].b, i});
    }
    sort(ask.begin(), ask.end());
    vt<e>unchanged;
    vt<pii>changed;
    for(int i = 0; i < m; i++){
        if(!change[i])unchanged.pb(edge[i]);
        else changed.pb({i, edge[i].w});
    }
    sort(unchanged.begin(), unchanged.end());
    int l = 0;
    for(int i = 0; i < ask.size(); i++){
        while(l < unchanged.size() && unchanged[l].w >= ask[i].w){
            dsu.unon(unchanged[l].u, unchanged[l].v); l++;
        }
        for(auto j: idd){
            if(j > ask[i].id)break;
            edge[v[j].a].w = v[j].b;
        }
        int cnt = 0;
        for(int j = 0; j < changed.size(); j++){
            if(edge[changed[j].fi].w >= ask[i].w){
                dsu.unon(edge[changed[j].fi].u, edge[changed[j].fi].v);
                cnt++;
            }
        }
        ans[ask[i].id] = dsu.getsz(ask[i].s);
        forr(j, 0, cnt)dsu.rollback();
        for(int j = 0; j < changed.size(); j++)edge[changed[j].fi].w = changed[j].se;
    }
    for(int i = 0; i < v.size(); i++){
        if(v[i].id == 2)cout << ans[i] << "\n";
    }
    for(auto i: idd){
        
        if(v[i].id == 1){
            change[v[i].a] = false;
            edge[v[i].a].w = v[i].b;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    forr(i, 0, m){
        int u, v, w; cin >> u >> v >> w;
        edge.pb({u, v, w});
    }
    cin >> q;
    forr(i, 0, q){
        int idq, u, v; cin >> idq >> u >> v;
        if(idq == 1)--u;
        queries[i / sq].pb({idq, u, v});
        
    }
    for(int i = 0; i <= (q - 1) / sq; i++){
        solve(queries[i]);
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void solve(std::vector<qq>)':
bridges.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
bridges.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i < ask.size(); i++){
      |                    ~~^~~~~~~~~~~~
bridges.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<e>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         while(l < unchanged.size() && unchanged[l].w >= ask[i].w){
      |               ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j = 0; j < changed.size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~
bridges.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j = 0; j < changed.size(); j++)edge[changed[j].fi].w = changed[j].se;
      |                        ~~^~~~~~~~~~~~~~~~
bridges.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~

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