제출 #975347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975347		imarn	자매 도시 (APIO20_swap)	C++14	0 / 100	197 ms	25184 KiB

swap

#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=1e5+5;
struct segment{
    int t[2*mxn]{0};
    void upd(int i,int amt,int sz){
        i+=sz;t[i]=amt;
        for(i>>=1;i;i>>=1)t[i]=max(t[2*i],t[2*i+1]);
    }
    int qr(int l,int r,int sz,int rs=0){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)rs=max(rs,t[l++]);
            if(r&1)rs=max(rs,t[--r]);
        }return rs;
    }
}seg;
struct lazy{
    int t[4*mxn]{0},lz[4*mxn]{0};
    void build(){
        for(int i=0;i<4*mxn;i++)t[i]=lz[i]=2e9;
    }
    void push(int i,int l,int r){
        t[i]=min(t[i],lz[i]);
        if(l<r)lz[2*i]=min(lz[2*i],lz[i]),lz[2*i+1]=min(lz[2*i+1],lz[i]);
        lz[i]=2e9;
    }
    void upd(int i,int l,int r,int tl,int tr,int v){
        push(i,l,r);
        if(r<tl||l>tr)return;
        if(r<=tr&&l>=tl){
            lz[i]=min(lz[i],v);push(i,l,r);return;
        }int m=(l+r)>>1;upd(2*i,l,m,tl,tr,v);upd(2*i+1,m+1,r,tl,tr,v);
        t[i]=min(t[2*i],t[2*i+1]);
    }
    int qr(int i,int l,int r,int tl,int tr){
        push(i,l,r);
        if(r<tl||l>tr)return 2e9;
        if(r<=tr&&l>=tl)return t[i];
        int m=(l+r)>>1;
        return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
    }
}lseg;
vector<pii>g[mxn];
int up[mxn]{0},pr[mxn]{0},dep[mxn]{0},head[mxn]{0},id[mxn]{0},ct=0,sz[mxn]{0},a[mxn]{0},n;
int get(int r){
    return up[r]==r?r:up[r]=get(up[r]);
}
void dfs(int u,int p,int l){
    pr[u]=p;dep[u]=l;sz[u]=1;
    for(auto v:g[u]){
        if(v.f==p)continue;
        dfs(v.f,u,l+1);
        a[v.f]=v.s;sz[u]+=sz[v.f];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;id[u]=++ct;
    int hv=-1,hc=-1;
    for(auto v:g[u]){
        if(v.f!=p&&sz[v.f]>hc)hc=sz[v.f],hv=v.f;
    }
    if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v.f==p||v.f==hv)continue;
        hld(v.f,u,v.f);
    }
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n=N;vector<pair<int,pii>>ed,bin;for(int i=0;i<N;i++)up[i]=i;
    for(int i=0;i<M;i++)ed.pb({W[i],{U[i],V[i]}});
    sort(ed.begin(),ed.end());
    for(auto it : ed){
        int u=get(it.s.f),v=get(it.s.s);
        if(u==v){bin.pb(it);continue;}
        up[u]=v;g[it.s.f].pb({it.s.s,it.f});
        g[it.s.s].pb({it.s.f,it.f});
    }dfs(0,0,0);hld(0,0,0);for(int i=0;i<N;i++)seg.upd(id[i]-1,a[i],N);
    lseg.build();
    for(auto it : bin){
        int u=it.s.f,v=it.s.s;
        while(head[u]!=head[v]){
            if(dep[head[u]]<dep[head[v]])swap(u,v);
            lseg.upd(1,1,N,id[head[u]],id[u],it.f);
            u=pr[head[u]];
        }
        if(dep[u]>dep[v])swap(u,v);
        lseg.upd(1,1,N,id[u]+1,id[v],it.f);
    }
}
int getMinimumFuelCapacity(int X, int Y){
    int rs1=0,rs2=2e9,x=X,y=Y;
    while(head[x]!=head[y]){
        if(dep[head[x]]<dep[head[y]])swap(x,y);
        rs1=max(rs1,seg.qr(id[head[x]]-1,id[x],n));
        rs2=min(rs2,lseg.qr(1,1,n,id[head[x]],id[x]));
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    rs1=max(rs1,seg.qr(id[x],id[y],n));
    rs2=min(rs2,lseg.qr(1,1,n,id[x]+1,id[y]));
    if(rs2==2e9)return -1;
    return -1;
}

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