Submission #1197465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197465		Malix	Swapping Cities (APIO20_swap)	C++20	13 / 100	386 ms	73036 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,k,v1=1,v2=1;
vii p,X,Z,arr;
vector<vector<pi>> a;
vi val,low,num;
vector<set<int>> st;
int nx=inf;

void dfs(int x){
  num[x]=v1++;
  for(auto u:a[x])if(p[x][0]!=u.F){
    p[u.F][0]=x;
    X[u.F][0]=u.S;
    dfs(u.F);
  }
  low[x]=v2++;
}

void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n=N;
  k=log2(n)+1;
  low.resize(n,0);
  num.resize(n,0);
  p.resize(n,vi(k,-1));
  X.resize(n,vi(k,0));
  Z.resize(n,vi(k,inf));
  a.resize(n);val.resize(n,inf);st.resize(n);
  vector<vector<pi>> b(n);arr.resize(n);
  REP(i,0,M){
    b[U[i]].PB({W[i],V[i]});
    b[V[i]].PB({W[i],U[i]});
  }
  priority_queue<ti,vector<ti>,greater<ti>> pq;
  vi dn(n,0);
  dn[0]=1;
  for(auto u:b[0])pq.push({u.F,u.S,0});
  while(!pq.empty()){
    int x=get<0>(pq.top());
    int y=get<1>(pq.top());
    int z=get<2>(pq.top());
    pq.pop();
    if(dn[y])continue;
    a[y].PB({z,x});
    a[z].PB({y,x});
    arr[y].PB(x);
    arr[z].PB(x);
    st[y].insert(z);
    st[z].insert(y);
    dn[y]=1;
    for(auto u:b[y])if(dn[u.S]==0)pq.push({u.F,u.S,y});
  }
  REP(i,0,M)if(st[U[i]].count(V[i])==0)nx=min(nx,W[i]);
  dfs(0);
  REP(i,0,n){
    int mn1=inf,mn2=inf;
    for(auto u:a[i])if(p[i][0]!=u.F){
      if(mn1>u.S){
        mn2=mn1;
        mn1=u.S;
      }
      else mn2=min(mn2,u.S);
    }
    if(a[i].size()>2)val[i]=mn2;
    for(auto u:a[i])if(p[i][0]!=u.F){
      Z[u.F][0]=mn1;
      if(u.S==mn1)Z[u.F][0]=mn2;
    }
  }
  REP(j,1,k)REP(i,0,n)if(p[i][j-1]!=-1){
    p[i][j]=p[p[i][j-1]][j-1];
    X[i][j]=max(X[i][j-1],X[p[i][j-1]][j-1]);
    Z[i][j]=min(Z[i][j-1],Z[p[i][j-1]][j-1]);
  }
  REP(i,0,n)sort(arr[i].begin(),arr[i].end());
}

bool ances(int x,int y){
  if(y==-1)return 1;
  if(x==-1)return 0;
  return (num[y]<=num[x]&&low[y]>=low[x]);
}

int getMinimumFuelCapacity(int x, int y) {
  int ans=0,ans2=nx;
  if(ances(x,y))ans2=min(ans2,val[x]);
  else if(ances(y,x))ans2=min(ans2,val[y]);
  else ans2=min(ans2,min(val[x],val[y]));
  for(int i=k-1;i>=0;i--)if(!ances(y,p[x][i])){
    ans=max(ans,X[x][i]);
    ans2=min(ans2,Z[x][i]);
    x=p[x][i];
  }
  for(int i=k-1;i>=0;i--)if(!ances(x,p[y][i])){
    ans=max(ans,X[y][i]);
    ans2=min(ans2,Z[y][i]);
    y=p[y][i];
  }
  if(ances(y,x))swap(x,y);
  ans=max(ans,X[x][0]);
  if(!ances(x,y)){
    ans=max(ans,X[y][0]);
    int tmp=p[x][0];
    if(arr[tmp].size()>2){
      if(arr[tmp][0]==X[x][0]){
        if(arr[tmp][1]!=X[y][0])ans2=min(ans2,arr[tmp][1]);
        else ans2=min(ans2,arr[tmp][2]);
      }
      else if(arr[tmp][0]==X[y][0]){
        if(arr[tmp][1]!=X[x][0])ans2=min(ans2,arr[tmp][1]);
        else ans2=min(ans2,arr[tmp][2]);
      }
      else ans2=min(ans2,arr[tmp][0]);
    }
  }
  else{
    int tmp=p[x][0];
    if(arr[tmp].size()>2){
      if(arr[tmp][0]==X[x][0]||arr[tmp][1]==X[x][0])ans2=min(ans2,arr[tmp][2]);
      else ans2=min(ans2,arr[tmp][1]);
    }
  }
  if(max(ans,ans2)==inf)return -1;
  return max(ans,ans2);
}

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