제출 #990116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990116		huutuan	철로 (IOI14_rail)	C++14	30 / 100	287 ms	196944 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

const int N=5010;
int n, d[N][N], adj[N][N];
pair<int, int> opt[N];

void findLocation(int N_, int first, int pos[], int t[])
{
   memset(adj, -1, sizeof adj);
   n=N_;
   for (int i=0; i<n; ++i){
      pos[i]=-1;
      for (int j=i+1; j<n; ++j) d[i][j]=d[j][i]=getDistance(i, j);
   }
   pos[0]=first;
   t[0]=1;
   for (int i=0; i<n; ++i){
      opt[i]={(int)1e9, (int)1e9};
      for (int j=0; j<n; ++j) if (i!=j){
         opt[i]=min(opt[i], {d[i][j], j});
      }
   }
   int ir=opt[0].second, il=opt[ir].second;
   pos[ir]=pos[0]+opt[0].first; pos[il]=pos[ir]-opt[ir].first; t[il]=1; t[ir]=2;
   vector<int> vl, vr;
   for (int i=0; i<n; ++i) if (i!=ir && i!=il){
      if (d[il][i]>d[ir][i]){
         vl.push_back(i);
      }else{
         vr.push_back(i);
      }
   }
   while ((int)vr.size()){
      pair<int, int> mn={(int)1e9, (int)1e9};
      for (int i:vr) mn=min(mn, {d[i][ir], i});
      int id=mn.second;
      pos[id]=pos[ir]+mn.first-opt[ir].first*2; t[id]=2;
      for (int i=0; i<n; ++i) if (opt[i].second==id){
         pos[i]=pos[id]-opt[i].first;
         t[id]=1;
      }
      ir=id;
      vr.erase(find(vr.begin(), vr.end(), id));
   }
   while ((int)vl.size()){
      pair<int, int> mn={(int)1e9, (int)1e9};
      for (int i:vl) mn=min(mn, {d[i][il], i});
      int id=mn.second;
      pos[id]=pos[il]-mn.first+opt[il].first*2; t[id]=1;
      for (int i=0; i<n; ++i) if (opt[i].second==id){
         pos[i]=pos[id]+opt[i].first;
         t[id]=2;
      }
      il=id;
      vl.erase(find(vl.begin(), vl.end(), id));
   }
}

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