Submission #566151

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

map<int,int> zauz;

void findLocation(int n, int first, int location[], int stype[])
{
    location[0]=first,stype[0]=1,zauz[first]=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,zauz[location[R]]=stype[R];
    bool skip=true;

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

        if (zauz[location[L]+(d(L,R)+d(L,k)-d(R,k))/2]==1) location[k]=location[L]+d(L,k),stype[k]=2;
        else if (zauz[location[R]-(d(L,R)+d(R,k)-d(L,k))/2]==2) location[k]=location[R]-d(R,k),stype[k]=1;
        else if (d(L,R)+d(0,k)-d(0,R)==d(L,k)) location[k]=location[L]+d(L,k),stype[k]=2;
        else location[k]=location[R]-d(R,k),stype[k]=1;

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

/*

4
4
1 1
1 2
2 5
2 6

*/

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: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44