제출 #1305859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305859		StefanSebez	자매 도시 (APIO20_swap)	C++20	0 / 100	2096 ms	33464 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
int N=1e5+50;
int n,m;
vector<array<int,3>>grane;
struct PersistentArray{
    vector<vector<pair<int,int>>>a;
    int tm=0;
    PersistentArray(){}
    PersistentArray(int n){a.assign(n,{{0,0}});}
    PersistentArray(vector<int>b){int n=b.size();a.resize(n);for(int i=0;i<n;i++)a[i].pb({b[i],0});}
    void Set(int i,int x){tm++;a[i].pb({x,tm});}
    void Add(int i,int x){tm++;a[i].pb({a[i].back().fi+x,tm});}
    int Get(int i,int t){
        int l=0,r=(int)a[i].size()-1,res=0;
        while(l<=r){
            int mid=l+r>>1;
            if(a[i][mid].se<=t)res=a[i][mid].fi,l=mid+1;
            else r=mid-1;
        }
        return res;
    }
    int Getlast(int i){return a[i].back().fi;}
};
struct DSU{
    PersistentArray par,sajz,ciklus,deg;
    vector<array<int,4>>times;
    DSU(){}
    DSU(int n){
        par=PersistentArray(n);
        sajz=PersistentArray(vector<int>(n,1));
        ciklus=PersistentArray(n);
        deg=PersistentArray(n);
        times.pb({0,0,0,0});
    }
    int FS(int u,int t){int p=par.Get(u,times[t][0]);if(p==0)return u;return FS(p,t);}
    void US(int u,int v){
        auto [t0,t1,t2,t3]=times.back();
        int u1=u,v1=v;
        deg.Add(u1,1);
        deg.Add(v1,1);
        u=FS(u,times.size()-1),v=FS(v,times.size()-1);
        if(u==v){
            ciklus.Set(u,1);
            times.pb({par.tm,sajz.tm,ciklus.tm,deg.tm});
            return;
        }
        int mx=max(deg.Get(u1,t3),deg.Get(v1,t3));
        if(sajz.Get(u,t1)>sajz.Get(v,t1))swap(u,v);
        par.Set(u,v);
        sajz.Add(v,sajz.Get(v,t1));
        if(mx>=3||ciklus.Get(v,t1))ciklus.Set(v,1);
        times.pb({par.tm,sajz.tm,ciklus.tm,deg.tm});
    }
    int Getcomp(int u,int t){return FS(u,t);}
    int Get(int u,int t){
        u=FS(u,t);
        return ciklus.Get(u,times[t][2]);
    }
}dsu;
void init(int n1,int m1,vector<int>U,vector<int>V,vector<int>W){
    n=n1,m=m1;
    for(int i=0;i<m;i++)grane.pb({W[i],U[i],V[i]});
    sort(grane.begin(),grane.end());
    dsu=DSU(N);
    for(auto [w,u,v]:grane){
        dsu.US(u,v);
        //printf("%i %i %i\n",u,v,w);
    }
    //printf("* %i\n",dsu.times.size());
}
int getMinimumFuelCapacity(int X, int Y){
    int l=1,r=m,ind=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(dsu.Getcomp(X,mid)==dsu.Getcomp(Y,mid)&&dsu.Get(X,mid))ind=mid,r=mid-1;
        else l=mid+1;
    }
    ind--;
    //printf(" %i\n",ind);
    if(ind<0)return -1;
    return grane[ind][0];
}

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