제출 #564817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
564817		hoanghq2004	철로 (IOI14_rail)	C++14	56 / 100	983 ms	98892 KiB

rail

/* This is sample grader for the contestant */
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL

#ifndef LOCAL
#include "rail.h"

#endif // LOCAL
#ifdef LOCAL



typedef struct Station {
  int index;
  int type;
  int location;
  int L,R;
}STATION;
long long cnt;
static int S,SUBTASK;
static STATION stations[10004];

int cmp_fun_1(const void *a,const void *b)
{
	STATION c,d;
	c = *(STATION*)(a);
	d = *(STATION*)(b);
  	return c.location < d.location ? -1 : 1;
}

int cmp_fun_2(const void *a,const void *b)
{
	STATION c,d;
	c = *(STATION*)(a);
	d = *(STATION*)(b);
  	return c.index < d.index ? -1 : 1;
}

void now_I_want_to_getLR(){
  int now = stations[S-1].index,i;
  for(i=S-2;i>=0;i--){
    stations[i].R = now;
    if(stations[i].type==2)	now = stations[i].index;
  }
  now = stations[0].index;
  for(i=1;i<S;i++){
    stations[i].L = now;
    if(stations[i].type==1)	now = stations[i].index;
  }
}

int getDistance(int x,int y)
{
  cnt++;
  if(x==y)	return 0;
  if(x<0 || x>=S || y<0 || y>=S)    return -1;
  if(stations[x].location > stations[y].location){
  	int tmp = x;
	x = y;
	y = tmp;
  }
  int ret = 0;
  if(stations[x].type==1 && stations[y].type==1){
    ret = stations[stations[y].R].location-stations[x].location+stations[stations[y].R].location-stations[y].location;
  }else if(stations[x].type==1 && stations[y].type==2){
    ret = stations[y].location-stations[x].location;
  }else if(stations[x].type==2 && stations[y].type==2){
    ret = stations[x].location-stations[stations[x].L].location+stations[y].location-stations[stations[x].L].location;
  }else if(stations[x].type==2 && stations[y].type==1){
    ret = stations[x].location-stations[stations[x].L].location+stations[stations[y].R].location
      -stations[stations[x].L].location+stations[stations[y].R].location-stations[y].location;
  }
  return ret;
}
#endif

const int N = 5010;
int d[N][N];

int par[N];

int Find(int u) {
    return (u == par[u] ? u : par[u] = Find(par[u]));
}

int Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return 0;
    par[v] = u;
    return 1;
}

int vis[N], mind[N];

void findLocation(int n, int first, int location[], int stype[]) {
    memset(d, -1, sizeof(d));
    auto get = [&](int u, int v) {
        if (u == v) return 0;
        if (u > v) swap(u, v);
        if (d[u][v] == -1) d[u][v] = getDistance(u, v);
        return d[u][v];
    };
    location[0] = first;
    stype[0] = 1;
    for (int i = 0; i < n; ++i) mind[i] = 1e9;
    auto add = [&](int u) {
        for (int v = 0; v < n; ++v)
            mind[v] = min(mind[v], get(u, v));
        vis[u] = 1;
    };
    add(0);
    for (int T = 1; T < n; ++T) {
        int u = -1;
        for (int v = 0; v < n; ++v)
            if (vis[v] == 0 && (u == -1 || mind[u] > mind[v])) u = v;
        int v = -1;
        for (int w = 0; w < n; ++w)
            if (vis[w] && get(u, w) == mind[u]) v = w;
        stype[u] = 3 - stype[v];
        if (stype[u] == 2) location[u] = location[v] + get(u, v);
        else location[u] = location[v] - get(u, v);
        add(u);
    }
//    for (int u = 0; u < n; ++u) cout << location[u] << ' ';
}
#ifdef LOCAL


void getInput()
{
  int g;
  g = scanf("%d",&SUBTASK);
  g = scanf("%d",&S);
  int s;
  for (s = 0; s < S; s++) {
    int type, location;
    g = scanf(" %d %d",&type,&location);
    stations[s].index = s;
    stations[s].location = location;
    stations[s].type = type;
    stations[s].L = -1;
    stations[s].R = -1;
  }
  qsort(stations, S, sizeof(STATION), cmp_fun_1);
  now_I_want_to_getLR();
  qsort(stations, S, sizeof(STATION), cmp_fun_2);
}

int serverGetStationNumber()
{
  return S;
}

int serverGetSubtaskNumber()
{
  return SUBTASK;
}

int serverGetFirstStationLocation()
{
  return stations[0].location;
}

int main()
{
  int i;
  getInput();
  cnt = 0;

  int location[10005];
  int type[10005];
  int ok = 1;
  findLocation(S, serverGetFirstStationLocation(),location, type);
  if(SUBTASK==3 && cnt>S*(S-1))	ok = 0;
  if(SUBTASK==4 && cnt>3*(S-1))	ok = 0;


  for (i = 0; i < S; i++)
    if(type[i]!=stations[i].type || location[i]!=stations[i].location)
      ok = 0;
  if(ok==0)	printf("Incorrect");
  else	printf("Correct");
  return 0;
}
#endif // LOCAL

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