Submission #1030206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030206		boyliguanhan	Swapping Cities (APIO20_swap)	C++17	100 / 100	438 ms	63284 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
vector<tuple<int,int,int>> edg;
int minyes[100100],abp[100100];
map<int,int> unpersist[100100];
vector<int>v[100100];
vector<pair<int,int>> roots;
int derot,N_;
void upd(int t,int p,int v){
    unpersist[p][t]=v;
}
void do_a_merge(int &x,int &y,int t){
    if(v[x].size()<v[y].size())
        swap(x,y);
    for(auto k:v[y])
        upd(t,k,x),abp[k]=x,v[x].push_back(k);
    v[y].clear();
}
int par[100100],deg[100100];
bitset<100100>yes;
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W) {
    for(int i=1;i<=N;i++)
        unpersist[i][-1]=i,abp[i]=i;
    N_=N;
    for(int i=1;i<=N;i++)
        v[i].push_back(i);
    for(int i=0;i<M;i++)
        edg.push_back({W[i],++U[i],++V[i]});
    for(auto&i:minyes)i=1e9+1;
    sort(edg.begin(),edg.end());
    int prevW=get<0>(edg[0]);
    for(auto[w,u,v]:edg){
        deg[u]++,deg[v]++;
        if(deg[u]>2&&!yes[abp[u]])
            yes[abp[u]]=1,minyes[abp[u]]=w;
        if(deg[v]>2&&!yes[abp[v]])
            yes[abp[v]]=1,minyes[abp[v]]=w;
        u=abp[u],v=abp[v];
        if(u-v) {
            do_a_merge(u,v,w);
            if(!yes[u]&&yes[v])
                yes[u]=1,minyes[u]=w;
        } else if(!yes[v])
            yes[v]=1,minyes[v]=w;
        prevW=w;
    }
}
int ok(int t,int x,int y){
    x=(--unpersist[x].upper_bound(t))->second;
    y=(--unpersist[y].upper_bound(t))->second;
    return x==y&&minyes[x]<=t;
}
int getMinimumFuelCapacity(int X,int Y) {
    ++X,++Y;
    int l=1,r=1e9,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(ok(mid,X,Y)){
            r=mid-1,res=mid;
        } else {
            l=mid+1;
        }
    }
    return res;
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:33:9: warning: variable 'prevW' set but not used [-Wunused-but-set-variable]
   33 |     int prevW=get<0>(edg[0]);
      |         ^~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:59:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid=l+r>>1;
      |                 ~^~

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