Submission #798655

#	Time	Username	Problem	Language	Result	Execution time	Memory
798655		TimDee	Rail (IOI14_rail)	C++17	100 / 100	116 ms	764 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

#define pi pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
int ask(int i, int j) {
  return getDistance(i,j);
}
void findLocation(int n, int p, int ans[], int type[]) {

  if (n==1) {
    ans[0]=p, type[0]=1; return;
  }
  
  vector<int> a(n), b(n), c(n);
  vector<int> vis(n,0); vis[0]=1;
  int f=0,s=1;
  forn(i,n) {
    if (vis[i]) continue;
    a[i]=ask(0,i);
    if (a[i] < a[s]) s=i;
  }
  vis[s]=1;
  b[0]=a[s];
  forn(i,n) {
    if (vis[i]) continue;
    b[i]=ask(s,i);
    if (b[i]<b[f]) f=i;
  }
  vis[f]=1;

  ans[0]=p, type[0]=1;
  ans[s]=p+a[s], type[s]=2;
  ans[f]=ans[s]-b[f], type[f]=1;

  vector<pi> l,r;

  c[0]=a[f], c[s]=b[f];
  forn(i,n) {
    if (vis[i]) continue;
    int x=a[i], y=b[i], z=b[f];
    if (x==a[s]+y) {
      l.pb({y,i});
      c[i]=y+z;
    } else if (y==x-a[s]+2*z) {
      r.pb({y-z,i});
      c[i]=y-z;
    } else assert(0);
  }
  
  sort(all(r));
  sort(all(l));

  int u,v;

  u=f, v=s;
  for(auto&it:r) {
    int d=it.f, i=it.s;
    int x=d, y=ask(v,i);
    int m=v;
    forn(j,n) {
      if (!vis[j]) continue;
      if (type[j]!=2) continue;
      if (ans[j] < ans[v]-y) continue;
      if (ans[j] < ans[m]) m=j;
    }
    if (x == ans[m]-ans[u]+ans[m]-(ans[v]-y)) {
      type[i]=1;
      ans[i]=ans[v]-y;
    } else {
      type[i]=2;
      ans[i]=ans[u]+x;
      v=i;
    }
    vis[i]=1;
  }

  u=f,v=s;
  for(auto&it:l) {
    int d=it.f, i=it.s;
    int x=d, y=ask(u,i);
    int m=u;
    forn(j,n) {
      if (!vis[j]) continue;
      if (type[j]!=1) continue;
      if (ans[j] > ans[u]+y) continue;
      if (ans[j] > ans[m]) m=j;
    }
    if (x == ans[v]-ans[m]+(ans[u]+y)-ans[m]) {
      type[i]=2;
      ans[i]=ans[u]+y;
    } else {
      type[i]=1;
      ans[i]=ans[v]-x;
      u=i;
    }
    vis[i]=1;
  }

}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44