Submission #418738

#	Time	Username	Problem	Language	Result	Execution time	Memory
418738		Malheiros	Bridges (APIO19_bridges)	C++17	0 / 100	3086 ms	87776 KiB

bridges

#include <bits/stdc++.h>
 
using namespace std;

#define ld long double
#define ll long long
//#define int ll
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second
#define PB push_back
#define MP make_pair
#define all(cont) cont.begin(),cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define FOR(i, j) for(int i=0;i<j;i++)
#define RFOR(i, j) for (int i=j;i>=0;i--)
#define GO cin.tie(NULL);
#define FAST ios_base::sync_with_stdio(false);
typedef pair<int,int> pii;
 


// Your function
//DEBBUGGING STUFF, JUST USE deb(a,b,c) and it will print the variables;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
    cout<<endl;
}

struct DSU{
    int* arr;
    int* size;
    stack<vector<pair<int,int>>> rb;
    int cc;
    DSU(int n){
        cc=n-1;
        arr = new int[n];
        for (int i=0;i<n;i++){
            arr[i]=-1;
        }
        rb.push(vector<pair<int,int>>());
    }
    int find(int a){
        while(arr[a]>=0)a=arr[a];
        return a;
    }
    void uniao(int a,int b){
        int paia=find(a);
        int paib=find(b);
        if (paia==paib)return;
        cc--;
        int tam=arr[paia]+arr[paib];
        if (arr[paia]>arr[paib]){
            rb.top().push_back({paib,arr[paib]});
            rb.top().push_back({paia,arr[paia]});
            arr[paia]=paib;
            arr[paib]=tam;
        }
        else{
            rb.top().push_back({paib,arr[paib]});
            rb.top().push_back({paia,arr[paia]});
            arr[paib]=paia;
            arr[paia]=tam;
        }
    }
    void persist(){
        rb.push(vector<pair<int,int>>());
    }
    void rollback(){
        auto changes=rb.top();
        rb.pop();
        int n=changes.size();
        cc+=n/2;
        for (int i=n-1;i>=0;i--){
            arr[changes[i].first]=changes[i].second;
        }
    }
};


const int maxn=5e4+10;
const int magic=230;

vector<pair<int,pii>> edges;

//qup =query update has index, {bridge , novo peso}
//qq = query query has {peso,node} index;
void solve(vector<pair<int,pii>>&qup,vector<pair<pii,int>>&qq){
    vector<pii> ans;
    vector<pair<int,pii>> unch;
    unordered_set<int> ss;
    for (auto k:qup){
        ss.insert(k.SF);
    }
   // int MMM=maxn;
    DSU dsu=DSU(maxn);
    vector<int> changed;
    FOR(i,edges.size()){
        if (ss.find(i)==ss.end()){
            unch.PB(edges[i]);
        }
        else changed.PB(i);
    }
    sort(unch.rbegin(),unch.rend());
    sort(qq.rbegin(),qq.rend());
    
    int j=0;
    for (auto k:qq){
        //cout<<"unindo"<<" ";
        //deb(k.FF,k.FS,k.second);
        for (;j<unch.size();j++){
            
            if (unch[j].first>=k.FF){
                //deb(unch[j].SF,unch[j].SS);
                dsu.uniao(unch[j].SF,unch[j].SS);
            }
            else break;
        }
        vector<pair<int,int>> mudei;
        for (auto k1:qup){
            if (k1.first<k.second){
                mudei.PB({k1.SF,edges[k1.SF].first});
                edges[k1.SF].first=k1.SS;
            }
            //else break;
        }
        dsu.persist();
        for (auto k1:changed){
            //deb(k1);
            if (edges[k1].first>=k.FF){
                //deb(edges[k1].SF,edges[k1].SS);
                dsu.uniao(edges[k1].SF,edges[k1].SS);
            }
        }
        ans.push_back({k.second,-dsu.arr[dsu.find(k.FS)]});
        dsu.rollback();
        for (auto k:mudei){
            edges[k.first].first=k.second;
        }
        //cout<<endl;
    }
    sort(ans.begin(),ans.end());
    for (auto k:qup){
        edges[k.SF].first=k.SS;
    }
    for (auto k:ans) cout<<k.second<<'\n';
}

int main(){
    GO FAST
    int n,m;
    cin>>n>>m;
    FOR(i,m){
        int a,b,c;cin>>a>>b>>c;
        edges.PB({c,{a,b}});
    }
    int q;cin>>q;
    int i=0;
    while(q>i){
        vector<pair<int,pii>> q1;
        vector<pair<pii,int>> q2;
        int t=0;
        for (int j=i;j<min(i+magic,q);j++){
            int a,b,c;cin>>a;
            if (a==1){
                int bridge,peso;
                cin>>bridge>>peso;
                q1.PB({t++,{bridge-1,peso}});
            }
            else{
                int ilha,peso;cin>>ilha>>peso;
                q2.PB({{peso,ilha},t++});
            }
        }
        solve(q1,q2);
        i+=magic;
    }
   // cout<<'\n';
}

Compilation message (stderr)

bridges.cpp: In function 'void solve(std::vector<std::pair<int, std::pair<int, int> > >&, std::vector<std::pair<std::pair<int, int>, int> >&)':
bridges.cpp:16:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define FOR(i, j) for(int i=0;i<j;i++)
......
  103 |     FOR(i,edges.size()){
      |         ~~~~~~~~~~~~~~          
bridges.cpp:103:5: note: in expansion of macro 'FOR'
  103 |     FOR(i,edges.size()){
      |     ^~~
bridges.cpp:116:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (;j<unch.size();j++){
      |               ~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:169:19: warning: unused variable 'b' [-Wunused-variable]
  169 |             int a,b,c;cin>>a;
      |                   ^
bridges.cpp:169:21: warning: unused variable 'c' [-Wunused-variable]
  169 |             int a,b,c;cin>>a;
      |                     ^

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