Submission #492467

#	Time	Username	Problem	Language	Result	Execution time	Memory
492467		Malheiros	Bridges (APIO19_bridges)	C++17	100 / 100	2666 ms	11196 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);
#define prec(x) cout << fixed << setprecision(x)
#define sz(x) (int)x.size()
 
typedef pair<int,int> pii;
typedef vector<int> VI;
typedef vector<pii> VPII;
typedef vector<VI> VVI;
typedef priority_queue<int> max_heap;
typedef priority_queue<pii> max_heapii;
typedef priority_queue<int,VI,greater<int>> min_heap;
typedef priority_queue<pii,VPII,greater<pii>> min_heapii;
 
const long double PI = 3.14159265359;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b){return uniform_int_distribution<ll>(a, b)(rng);}
 
#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;
}
 
void print(vector<int>v){
	cout<<"[";
	FOR(i,v.size()){
		cout<<v[i];
		if(i+1!=v.size())cout<<", ";
	}
	cout<<"]"<<endl;
}
 
void print(pii p){
	cout<<"{"<<p.first<<", "<<p.second<<"}"<<endl;
}
 
struct DSU{
    int* arr;
    int* size;
    stack<vector<pair<int,int>>> rb;
    int cc;
    DSU(){
 
    }
    DSU(int n){
        cc=n;
        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--;
        //paib é maior, entao liga em b
        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=1e5+10;
const int magic=800;  
int ord[maxn];
int ans[maxn];
int n,m;
vector<pair<int,pii>> bridges;//{weight,{a,b}};
vector<pair<int,pii>> updates[magic];//{tempo,{qual,peso}};
vector<pair<int,pii>> queries[magic];//{peso,{tempo,qual}};
DSU dsu;
int mrds[maxn];
int mudanca[maxn];
void solve(int u,pair<int,pii> q){
  int it=0;
  VI mudei;
  while(it<sz(updates[u]) && updates[u][it].first<q.SF){
    mudanca[updates[u][it].SF]=updates[u][it].SS;
    mudei.PB(updates[u][it].SF);
    it++;
  }
  for(auto k1:updates[u]){
    auto k=k1.SF;
    if (mudanca[k]==0){
      if (bridges[k].first>=q.first){
        //deb(bridges[k].SS,bridges[k].SF);
        dsu.uniao(bridges[k].SS,bridges[k].SF);
      }
    }
    else{
      if (mudanca[k]>=q.first){
        //deb(bridges[k].SS,bridges[k].SF);
        dsu.uniao(bridges[k].SS,bridges[k].SF);
      }
    }
  }
  for(auto k:mudei) mudanca[k]=0;
  //deb(ord[q.SF]);
  ans[ord[q.SF]]=-dsu.arr[dsu.find(q.SS)];
}
 
void solve(int u){
  //deb(n,dsu.cc);
  for(auto k:updates[u]) mrds[k.SF]=1;
  vector<pii> unchanged;
  FOR(i,m){
    if (!mrds[i])unchanged.PB({bridges[i].first,i});
  }
  sort(rall(unchanged));
  sort(rall(queries[u]));
  auto it=0;
  dsu.persist();
  for(auto q:queries[u]){
    while(it<sz(unchanged)){
      if (unchanged[it].first>=q.first){
        //deb(bridges[it->second].SF,bridges[it->second].SS);
        dsu.uniao(bridges[unchanged[it].second].SF,bridges[unchanged[it].second].SS);
        it++;
      }
      else break;
    }
    //cout<<"PERSISTINDO"<<endl;
    dsu.persist();
    solve(u,q);
    //cout<<"ROLLBACK"<<endl;
    dsu.rollback();
  }
  dsu.rollback();
  for(auto k:updates[u]){
    mrds[k.SF]=0;
    bridges[k.SF].first=k.SS;
  }
}
 
signed main(){
  GO FAST
  cin>>n>>m;
  dsu=DSU(n);
  bridges=vector<pair<int,pii>>(m);
  FOR(i,m){
    int a,b,c;cin>>a>>b>>c;a--;b--;
    bridges[i]={c,{a,b}};
  }
  int q;cin>>q;
  int cont=0;
  FOR(i,q){
    int a,b,c;cin>>a>>b>>c;
    b--;
    if (a==1){//update
      updates[i/magic].push_back({i,{b,c}});
    }
    else{
        queries[i/magic].push_back({c,{i,b}});
        ord[i]=cont++;
    }
  }
  FOR(i,magic)if((!queries[i].empty()) ||  (!updates[i].empty()))solve(i);
  FOR(i,cont){
    cout<<ans[i]<<'\n';
  }
}

Compilation message (stderr)

bridges.cpp: In function 'void print(std::vector<int>)':
bridges.cpp:16:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define FOR(i, j) for(int i=0;i<j;i++)
......
   47 |  FOR(i,v.size()){
      |      ~~~~~~~~~~                 
bridges.cpp:47:2: note: in expansion of macro 'FOR'
   47 |  FOR(i,v.size()){
      |  ^~~
bridges.cpp:49:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   if(i+1!=v.size())cout<<", ";
      |      ~~~^~~~~~~~~~

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