Submission #565993

#	Time	Username	Problem	Language	Result	Execution time	Memory
565993		n0sk1ll	Rail (IOI14_rail)	C++14	0 / 100	85 ms	22364 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];
}

set<int> zauz;

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

    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,zauz.insert(R);
    bool skip=true;

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

        //cout<<L<<","<<R<<": "<<k<<endl;
        if (zauz.count(location[L]+(d(L,R)+d(k,L)-d(k,R))/2)) location[k]=location[L]+d(L,k),stype[k]=2;
        else location[k]=location[R]-d(R,k),stype[k]=1;

        zauz.insert(location[k]);
        if (location[k]>location[R]) R=k;
        if (location[k]<location[L]) L=k;
    }
}

Compilation message (stderr)

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

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