Submission #565946

#	Time	Username	Problem	Language	Result	Execution time	Memory
565946		n0sk1ll	Rail (IOI14_rail)	C++14	8 / 100	81 ms	16860 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

#define xx first
#define yy second

using namespace std;
long long int typedef li;

int dist[5003][5003];

int d(int i, int j)
{
    if (i>j) swap(i,j);
    if (!dist[i][j]) dist[i][j]=getDistance(i,j);
    return dist[i][j];
}

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

    vector<pair<int,int>> ok;
    for (int i=1;i<n;i++) ok.push_back({d(0,i),i});
    sort(ok.begin(),ok.end());

    int L=0,R=ok.front().yy;
    location[R]=location[L]+d(L,R),stype[R]=2;
    bool skip=true;

    for (auto [di,k] : ok)
    {
        if (skip)
        {
            skip=false;
            continue;
        }

        if (d(k,L)<d(k,R))
        {
            location[k]=location[L]+d(L,k),stype[k]=2;
            if (d(k,L)>d(L,R)) R=k;
        }
        else
        {
            location[k]=location[R]-d(R,k),stype[k]=1;
            if (d(k,R)>d(L,R)) L=k;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [di,k] : ok)
      |               ^

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