제출 #289302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
289302		stoyan_malinin	철로 (IOI14_rail)	C++14	56 / 100	811 ms	98812 KiB

rail

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

#include <vector>
#include <cstring>
#include <assert.h>
#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], origin[MAXN];
bool done[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++)
    {
        //cout << " ---- " << lastDone << " ---- " << '\n';

        for(int x = 0;x<N;x++)
        {
            if(done[x]==true) continue;


            //cout << dist[x] << " != " << getDistance(x, lastDone) << '\n';
            //assert(ask(x, lastDone)!=dist[x]);
            if(ask(x, lastDone)<dist[x])
            {
                dist[x] = ask(x, lastDone);
                origin[x] = lastDone;

                //if(x==1) cout << " -> " << origin[x] << " || " << lastDone << '\n';
            }
        }

        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';
}
/*
1
6
1 2
1 3
1 1
2 4
2 5
2 6
*/

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