Submission #566216

#	Time	Username	Problem	Language	Result	Execution time	Memory
566216		zaneyu	Swapping Cities (APIO20_swap)	C++14	7 / 100	269 ms	24412 KiB

swap

/*input
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

*/
#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()
#define pii pair<int,int>
#define f first
#define s second
#define MXTO(a,b) a=max(a,b)
#define MNTO(a,b) a=min(a,b)
#define sz(x) (int)x.size()
#define pb push_back
const int maxn=1e5+5;
vector<pair<int,pii>> ed;
int n,m;
int par[maxn];
pair<bool,pii> cmp[maxn];
vector<int> vv[maxn];
int find(int u){
    if(par[u]==u) return u;
    return par[u]=find(par[u]);
}
vector<pii> sp[maxn];
int sc[maxn];
const int INF=0x3f3f3f3f;
void merge(int t,int a,int b){
    int oa=a,ob=b;
    a=find(a),b=find(b);
    if(a==b){
        if(sc[a]==INF) sc[a]=t;
        cmp[a].f=0;
        return;
    }
    if(sz(vv[a])<sz(vv[b])) swap(a,b);
    par[b]=a;
    if(cmp[a].f and cmp[b].f){
        if((oa==cmp[a].s.f or oa==cmp[a].s.s) and (ob==cmp[b].s.f or ob==cmp[b].s.s)){
            cmp[a].f=1;
            if(oa==cmp[a].s.f) cmp[a].s.f=cmp[a].s.s;
            if(ob==cmp[b].s.f) cmp[a].s.s=cmp[b].s.s;
            else cmp[a].s.s=cmp[b].s.f;
        }
        else{
            if(sc[a]==INF) sc[a]=t;
            cmp[a].f=0;
        }
    }
    else{
        if(sc[a]==INF) sc[a]=t;
        cmp[a].f=0;
    }
    for(int x:vv[b]) sp[x].pb({t,a}),vv[a].pb(x);
    vv[b].clear();
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N,m=M;
    REP(i,M){
        ed.pb({W[i],{U[i],V[i]}});
    }
    sort(ALL(ed));
    REP(i,n) par[i]=i,cmp[i]={1,{i,i}},vv[i].pb(i),sc[i]=INF,sp[i].pb({-1,i});
    REP(i,m){
        auto a=ed[i];
        merge(i,a.s.f,a.s.s);
    }
}
int gp(int x,int t){
    return (*prev(upper_bound(ALL(sp[x]),make_pair(t,INF)))).s;
}
int getMinimumFuelCapacity(int x, int y) {
    int l=0,r=m-1;
    int a=gp(x,m-1),b=gp(y,m-1);
    if(a!=b or sc[a]==INF){
        return -1;
    }
    while(l<r){
        int mid=(l+r)/2;
        int a=gp(x,mid),b=gp(y,mid);
        if(a==b and sc[a]<=mid) r=mid;
        else l=mid+1;
    }
    return ed[l].f;
}

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