Submission #1132245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132245		t9unkubj	Swapping Cities (APIO20_swap)	C++20	100 / 100	1352 ms	29064 KiB

swap

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
struct hairetu{
    vc<vc<pair<int,int>>>val;
    hairetu(int n=0):val(n,vc<pair<int,int>>(1,{(int)-2e9,0})){}
    //val[i]の時刻tにaをpushする
    void push(int i,int t,int a){
        val[i].push_back({t,a});
    }
    //val[i]の時刻tを見る
    int get(int i,int t){
        int ac=0,wa=val[i].size();
        while(wa-ac>1){
            int wj=ac+wa>>1;
            if(val[i][wj].first<=t)ac=wj;
            else wa=wj;
        }
        return val[i][ac].second;
    }
};
struct persisitent_uf{
    hairetu par;
    hairetu ok;
    persisitent_uf(int n=0):par(n),ok(n){
        rep(i,n){
            par.push(i,-1,-1);
        }
    }
    int root(int a,int t){
        if(par.get(a,t)<0)return a;
        return root(par.get(a,t),t);
    }
    int same(int a,int b,int t){
        a=root(a,t),b=root(b,t);
        return a==b;
    }
    int merge(int a,int b,int t){
        a=root(a,t),b=root(b,t);
        if(a==b)return 0;
        if(-par.get(a,t)<-par.get(b,t))swap(a,b);
        ok.push(a,t,ok.get(a,t)||ok.get(b,t));
        par.push(a,t,par.get(a,t)+par.get(b,t));
        par.push(b,t,a);
        return 1;    
    }
};
int n,m;
vc<int>u,v,w;
persisitent_uf uf;
int deg[(int)1e6];
vc<int>W;
void solve(){
    uf=persisitent_uf(n);
    vc<int>idx(m);
    iota(all(idx),0);
    sort(all(idx),[&](int i,int j){
        return w[i]<w[j];
    });
    for(auto&i:idx)W.push_back(w[i]);
    int T=0;
    for(auto&i:idx){
        deg[u[i]]++;
        deg[v[i]]++;
        if(uf.merge(u[i],v[i],T)==0){
            dbg(u[i],v[i]);
            uf.ok.push(uf.root(u[i],T),T,1);
        }
        if(deg[u[i]]==3){
            uf.ok.push(uf.root(u[i],T),T,1);
        }
        if(deg[v[i]]==3){
            uf.ok.push(uf.root(v[i],T),T,1);
        }
        T++;
    }
}
int answer(int x,int y){
    int ac=m,wa=-1;
    while(ac-wa>1){
        int wj=ac+wa>>1;
        if(uf.same(x,y,wj)&&uf.ok.get(uf.root(x,wj),wj))ac=wj;
        else wa=wj;
    }
    if(ac==m)return -1;
    return W[ac];
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N,m=M,u=U,v=V,w=W;
    solve();
}

int getMinimumFuelCapacity(int X, int Y) {
    return answer(X,Y);
  return 0;
}
namespace judge{
    void run(){
        #ifdef t9unkubj
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        #endif
        int n,m;
        cin>>n>>m;
        vc<int>u(m),v(m),w(m);
        rep(i,m)cin>>u[i]>>v[i]>>w[i];
        init(n,m,u,v,w);
        
        int q;
        cin>>q;
        while(q--){
            int x,y;
            cin>>x>>y;
            dbg(getMinimumFuelCapacity(x,y));
        }
    }
};
//int main(){judge::run();}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27