Submission #673769

#	Time	Username	Problem	Language	Result	Execution time	Memory
673769		Cookie	Bridges (APIO19_bridges)	C++14	100 / 100	2037 ms	12048 KiB

bridges

#include<bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#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 = 800, mxm = 1e5;
int n, m, q;
struct DSU{
    vt<pii>past_sz, past_p;
    int p[mxn + 1], sz[mxn + 1];
    void init(){
        memset(p, -1, sizeof(p));
        past_sz.clear(); past_p.clear();
    }
    int fp(int a){
        if(p[a] < 0)return(a);
        return(fp(p[a]));
    }
    int getsz(int pp){
        return(-p[fp(pp)]);
    }
    void unon(int u, int v){
        u = fp(u); v = fp(v);
        if(-p[u] < -p[v])swap(u, v);
        past_sz.pb({u, p[u]}); past_p.pb({v, p[v]});
        if(u != v){
            p[u] += p[v]; p[v] = u;
        }
    }
    void rollback(){
        p[past_p.back().fi] = past_p.back().se; past_p.pop_back();
        p[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;
    for(int i = 0; i < v.size(); i++){
        if(v[i].id == 1)change[v[i].a] = true;
        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(int j = 0; j < ask[i].id; j++){
            if(v[j].id == 1)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";
    }
    forr(i, 0, v.size()){
        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:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
bridges.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < ask.size(); i++){
      |                    ~~^~~~~~~~~~~~
bridges.cpp:90:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<e>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         while(l < unchanged.size() && unchanged[l].w >= ask[i].w){
      |               ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:97: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]
   97 |         for(int j = 0; j < changed.size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~
bridges.cpp:105: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]
  105 |         for(int j = 0; j < changed.size(); j++)edge[changed[j].fi].w = changed[j].se;
      |                        ~~^~~~~~~~~~~~~~~~
bridges.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
bridges.cpp:12:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define forr(i, a, b) for(int i = a; i < b; i++)
......
  110 |     forr(i, 0, v.size()){
      |          ~~~~~~~~~~~~~~                 
bridges.cpp:110:5: note: in expansion of macro 'forr'
  110 |     forr(i, 0, v.size()){
      |     ^~~~

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