Submission #975508

#	Time	Username	Problem	Language	Result	Execution time	Memory
975508		hirayuu_oj	Swapping Cities (APIO20_swap)	C++17	100 / 100	1489 ms	24248 KiB

swap

#include "swap.h"

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) x.begin(),x.end()
using ll=long long;

struct PersUF{
    int size;
    int time=-1;
    //時間,親,flg
    vector<vector<array<int,3>>> tree;
    PersUF(int sz){
        size=sz;
        tree.resize(sz,{{-1,-1,0}});
    }
    int root(int pos,int tim){
        while(true){
            int ok=0,ng=tree[pos].size();
            while(ng-ok>1){
                int mid=(ok+ng)/2;
                if(tree[pos][mid][0]<=tim){
                    ok=mid;
                }
                else{
                    ng=mid;
                }
            }
            if(tree[pos][ok][1]<0)return pos;
            pos=tree[pos][ok][1];
        }
    }
    int isok(int pos,int tim){
        while(true){
            int ok=0,ng=tree[pos].size();
            while(ng-ok>1){
                int mid=(ok+ng)/2;
                if(tree[pos][mid][0]<=tim){
                    ok=mid;
                }
                else{
                    ng=mid;
                }
            }
            if(tree[pos][ok][1]<0)return tree[pos][ok][2];
            pos=tree[pos][ok][1];
        }
    }
    bool same(int s,int t,int tim){
        return root(s,tim)==root(t,tim);
    }
    void merge(int s,int t){
        time++;
        s=root(s,time);
        t=root(t,time);
        if(s==t){
            if(tree[s].back()[2])return;
            tree[s].emplace_back(tree[s].back());
            tree[s].back()[0]=time;
            tree[s].back()[2]=1;
            return;
        }
        if(-tree[s].back()[1]<-tree[t].back()[1])swap(s,t);
        tree[s].emplace_back(tree[s].back());
        tree[t].emplace_back(tree[t].back());
        tree[s].back()[0]=time;
        tree[t].back()[0]=time;
        tree[s].back()[1]+=tree[t].back()[1];
        tree[t].back()[1]=s;
        tree[s].back()[2]|=tree[t].back()[2];
    }
};

vector<array<int,3>> edge;
PersUF uni(0);
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    uni=PersUF(N);
    edge.resize(M);
    rep(i,M){
        edge[i]={W[i],U[i],V[i]};
    }
    sort(all(edge));
    vector<int> cnt(N,0);
    for(auto &[w,u,v]:edge){
        uni.merge(u,v);
        cnt[u]++;
        cnt[v]++;
        if(cnt[u]>=3||cnt[v]>=3){
            int pos=uni.root(u,uni.time);
            uni.tree[pos].back()[2]=1;
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int ng=-1,ok=uni.time+1;
    while(ok-ng>1){
        int mid=(ok+ng)/2;
        bool can=0;
        if(uni.same(X,Y,mid)){
            if(uni.isok(X,mid))can=1;
        }
        if(can)ok=mid;
        else ng=mid;
    }
    if(ok==uni.time+1)return -1;
    return edge[ok][0];
}

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