Submission #209023

#	Time	Username	Problem	Language	Result	Execution time	Memory
209023		jtnydv25	Bridges (APIO19_bridges)	C++14	30 / 100	3079 ms	7548 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
    
#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double
    
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
    os<<"("<<p.first<<", "<<p.second<<")";
    return os;
}
    
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
    os<<"{";
    for(int i = 0;i < (int)v.size(); i++){
        if(i)os<<", ";
        os<<v[i];
    }
    os<<"}";
    return os;
}
    
#ifdef LOCAL
#define cerr cout
#else
#endif
    
#define TRACE
    
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
    
template<class T>
struct rollback_array{
    struct ct{
        int where; 
        T what;
    };
    stack<ct> changes;
    vector<T> arr;
    int n;
    rollback_array(){n = 0;}
    rollback_array(int n) : n(n), arr(n){};
    void setall(T x){
        for(int i = 0; i < n; i++) arr[i] = x;
    }
    // if not to be rolled back just do arr[x] = v
    int & operator [] (int x){ return arr[x];}
    inline void update(int i, T v){
        changes.push({i, arr[i]});
        arr[i] = v;
    }
    inline void click(){
        changes.push({-1, T()});
    }
    inline void roll_back(){
        while(!changes.empty()){
            auto it = changes.top();
            changes.pop();
            if(it.where == -1) return;
            arr[it.where] = it.what;
        }
    }
};
    
struct rollback_dsu{
    int n;
    rollback_array<int> par, num;
    rollback_dsu(int n) : n(n), par(n), num(n){
        par.setall(-1);
        num.setall(1);
    }
    int root(int x){
        if(par[x] == -1) return x;
        int rt = root(par[x]);
        par.update(x, rt);
        return rt;
    }
    void merge(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(num[x] > num[y]) swap(x, y);
        par.update(x, y);
        num.update(y, num[x] + num[y]);
    }
    void click(){
        par.click();
        num.click();
    }
    void roll_back(){
        par.roll_back();
        num.roll_back();
    }
};
    
const int N = 100005;
int a[N], b[N], w[2 * N];
int type[N], s[N];
bool changing[N];
const int BLOCK = 205;
int ans[N];
int temp[2 * N];
int cntr = 0;
    
void go(vector<int> & a, vector<int> & b){
    int pos_a = sz(a) - 1, pos_b = sz(b) - 1;
    cntr = 0;
    while(pos_a >= 0 || pos_b >= 0){
        if(pos_a >= 0 && (pos_b == -1 || w[a[pos_a]] >= w[b[pos_b]])){
            temp[cntr++] = a[pos_a--];
        }
        else{
            temp[cntr++] = b[pos_b--]; 
        }
    }
    for(int i = 1; i < cntr; i++) assert(w[temp[i]] <= w[temp[i - 1]]);
}
    
int main(){
    int n = 50000, m = 100000; 
    sd(n); sd(m);
    rollback_array<int> W(m);
    for(int i = 0; i < m; i++){
        sd(a[i]); sd(b[i]); sd(w[i]);
        a[i]--; b[i]--;
        W[i] = w[i];
    }
    int q = 100000; 
    sd(q);
    for(int i = 0; i < q; i++){
        sd(type[i]); sd(s[i]); sd(w[i + m]);
        s[i]--;
    }
    vector<int> perm(m); iota(all(perm), 0);
    sort(all(perm), [&](int i, int j){return w[i] < w[j];});
    rollback_dsu D(n);
    
    for(int i = 0; i * BLOCK < q; i++){
        int st = i * BLOCK, en = min(q - 1, st + BLOCK - 1);
        vector<int> queries;
        memset(changing, 0, sizeof changing);
        vector<int> changing_edges;
        for(int j = st; j <= en; j++){
            if(type[j] == 1){
                changing[s[j]] = 1;
            } else{
                queries.push_back(j + m);
            }
        }
        vector<int> v;
        for(int j = 0; j < m; j++){
            int ind = perm[j];
            if(changing[ind]){
                changing_edges.push_back(ind);
            } else{
                v.push_back(ind);
            }
        }
        sort(all(queries), [&](int p, int q){return w[p] < w[q];});
        
        go(v, queries);
        D.click();
        for(int j = 0; j < cntr; j++){
            if(j) assert(w[temp[j]] <= w[temp[j - 1]]);
            int ind = temp[j];
            if(ind < m){
                if(!changing[ind]){
                    D.merge(a[ind], b[ind]);
                }
            } else{
                ind -= m;
                D.click();
                W.click();
                for(int j = st; j < ind; j++){
                    if(type[j] == 1) W.update(s[j], w[j + m]);
                }
                for(int e : changing_edges) if(W[e] >= w[ind + m]){
                    D.merge(a[e], b[e]);
                }
                ans[ind] = D.num[D.root(s[ind])];
                D.roll_back();
                W.roll_back();
            }
        }
        D.roll_back();
        for(int j = st; j <= en; j++) if(type[j] == 1){
            w[s[j]] = w[j + m];
            W[s[j]] = w[j + m];
        }
        sort(all(changing_edges), [&](int p, int q){return w[p] < w[q];});
        go(v, changing_edges);
        for(int j = 0; j < m; j++) perm[j] = temp[m - 1 - j];
    }
    
    for(int i = 0; i < q; i++) if(type[i] == 2) printf("%d\n", ans[i]);
}

Compilation message (stderr)

bridges.cpp: In instantiation of 'rollback_array<T>::rollback_array(int) [with T = int]':
bridges.cpp:87:46:   required from here
bridges.cpp:59:9: warning: 'rollback_array<int>::n' will be initialized after [-Wreorder]
     int n;
         ^
bridges.cpp:58:15: warning:   'std::vector<int> rollback_array<int>::arr' [-Wreorder]
     vector<T> arr;
               ^~~
bridges.cpp:61:5: warning:   when initialized here [-Wreorder]
     rollback_array(int n) : n(n), arr(n){};
     ^~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:140:5: note: in expansion of macro 'sd'
     sd(n); sd(m);
     ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:140:12: note: in expansion of macro 'sd'
     sd(n); sd(m);
            ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:143:9: note: in expansion of macro 'sd'
         sd(a[i]); sd(b[i]); sd(w[i]);
         ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:143:19: note: in expansion of macro 'sd'
         sd(a[i]); sd(b[i]); sd(w[i]);
                   ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:143:29: note: in expansion of macro 'sd'
         sd(a[i]); sd(b[i]); sd(w[i]);
                             ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:148:5: note: in expansion of macro 'sd'
     sd(q);
     ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:150:9: note: in expansion of macro 'sd'
         sd(type[i]); sd(s[i]); sd(w[i + m]);
         ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:150:22: note: in expansion of macro 'sd'
         sd(type[i]); sd(s[i]); sd(w[i + m]);
                      ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:150:32: note: in expansion of macro 'sd'
         sd(type[i]); sd(s[i]); sd(w[i + m]);
                                ^~

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