Submission #289279

#	Time	Username	Problem	Language	Result	Execution time	Memory
289279		stoyan_malinin	Rail (IOI14_rail)	C++14	8 / 100	426 ms	98688 KiB

rail

#include "rail.h"
//#include "grader.cpp"

#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

const int MAXN = 5005;

int askedAlready[MAXN][MAXN];
int ask(int x, int y)
{
    if(x>y) swap(x, y);
    if(askedAlready[x][y]==-1) askedAlready[x][y] = getDistance(x, y);

    return askedAlready[x][y];
}

int dist[MAXN];
bool done[MAXN], origin[MAXN];

void findLocation(int N, int first, int location[], int stype[])
{
    memset(askedAlready, -1, sizeof(askedAlready));
    memset(done, false, sizeof(done));

    done[0] = true;

    stype[0] = 0;
    location[0] = first;

    int lastDone = 0;
    for(int i = 0;i<N;i++)
    {
        dist[i] = 1e9;
    }

    for(int iter = 0;iter<N-1;iter++)
    {
        for(int x = 0;x<N;x++)
        {
            if(done[x]==true) continue;
            if(getDistance(x, lastDone)<dist[x])
            {
                dist[x] = getDistance(x, lastDone);
                origin[x] = lastDone;
            }
        }

        int newDone = -1;
        for(int x = 0;x<N;x++)
        {
            if(done[x]==true) continue;
            if(newDone==-1 || dist[x]<dist[newDone]) newDone = x;
        }

        stype[newDone] = stype[ origin[newDone] ]^1;
        //cout << newDone << " from " << origin[newDone] << '\n';

        if(stype[ origin[newDone] ]==0)
            location[newDone] = location[ origin[newDone] ] + dist[newDone];
        else
            location[newDone] = location[ origin[newDone] ] - dist[newDone];

        done[newDone] = true;
        lastDone = newDone;
    }

    for(int i = 0;i<N;i++) stype[i]++;
    //for(int i = 0;i<N;i++)
    //    cout << i << " -> " << location[i] << " " << stype[i] << '\n';
}
/*
3
4
1 2
2 5
1 3
1 1
*/

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