제출 #371084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371084		idk321	철로 (IOI14_rail)	C++11	8 / 100	3093 ms	85100 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>
using namespace std;



const int N = 5005;
const int M = 1000005;
int dist[N][N];
int* location;
int* stype;
int n;

int cdist(int i, int j)
{
    if (i == j) return 0;
    if (dist[i][j] == 0)
    {
        dist[i][j] = getDistance(i, j);
        dist[j][i] = dist[i][j];
    }
    return dist[i][j];
}

int getNext(int x)
{
    int mi = M;
    int next = -1;
    for (int i = 0; i < n; i++)
    {
        if (cdist(x, i) < mi && i != x)
        {
            mi = cdist(x, i);
            next = i;
        }
    }

    if (next != -1)
    {
        if (stype[x] == 1)
        {
            location[next] = location[x] + mi;
            stype[next] = 2;
        } else
        {
            location[next] = location[x] - mi;
            stype[next] = 1;
        }
    }

    return next;
}

void findLocation(int n1, int first, int location1[], int stype1[])
{
    n = n1;
    location = location1;
    stype = stype1;
    location[0] = first;
    stype[0] = 1;

    if (n == 1) return;




    int l = 0;
    while (true)
    {
        int cur = getNext(l);

        int cl = -1;
        int mi = M;
        for (int i = 0; i < n; i++)
        {
            if (cdist(cur, i) < mi && cdist(cur, i) > cdist(l, cur) && cdist(l, i) > cdist(cur, i))
            {
                cl = i;
                mi = cdist(cur, i);
            }
        }

        if (cl == -1)
        {
            break;
        } else
        {
            l = cl;
            location[l] = location[cur] - mi;
            stype[l] = 1;
        }
    }

    int ml = l;

    int r = getNext(ml);
    while (true)
    {
        int cur = getNext(r);
        int cr = -1;
        int mi = M;
        for (int i = 0; i < n; i++)
        {
            if (cdist(cur, i) < mi && cdist(cur, i) > cdist(r, cur) && cdist(r, i) > cdist(cur, i))
            {
                cr = i;
                mi = cdist(cur, i);
            }
        }

        if (cr == -1)
        {
            break;
        } else
        {
            r = cr;
            location[r] = location[cur] + mi;
            stype[r] = 2;
        }
    }


    int mr = r;
    l = getNext(r);
    while (true)
    {
        int cur = getNext(l);

        int cl = -1;
        int mi = M;
        for (int i = 0; i < n; i++)
        {
            if (cdist(cur, i) < mi && cdist(cur, i) > cdist(l, cur) && cdist(l, i) > cdist(cur, i))
            {
                cl = i;
                mi = cdist(cur, i);
            }
        }

        if (cl == -1)
        {
            break;
        } else
        {
            l = cl;
            location[l] = location[cur] - mi;
            stype[l] = 1;
        }
    }


}

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:124:9: warning: unused variable 'mr' [-Wunused-variable]
  124 |     int mr = r;
      |         ^~

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