Submission #295343

#	Time	Username	Problem	Language	Result	Execution time	Memory
295343		arayi	Rail (IOI14_rail)	C++17	100 / 100	205 ms	41080 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
#define MP make_pair
#define ad push_back
#define sc second
#define fr first
using namespace std;

const int m = 1e6 + 10;
int n, fr, sm, sc;
int a[5010][5010];
pair<int, int> b[m];
bool col[5010];
int getmn(int aa)
{
    int mn = INT_MAX, ret = aa;
    for (int i = 0; i < n; i++)
    {
        if(aa == i) continue;
        if(a[aa][i] < mn) mn = a[aa][i], ret = i;
    }
    return ret;
}
vector <pair<int, int> > fp;
void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    fr = first;
    for (int i = 1; i < n; i++)
        a[0][i] = a[i][0] = getDistance(0, i);
    stype[0] = 1, location[0] = fr;
    if(n == 1) return;
    sm = getmn(0), sc = a[0][sm] + fr;
    stype[sm] = 2, location[sm] = sc;
    for (int i = 1; i < n; i++)
        if(i != sm) a[i][sm] = a[sm][i] = getDistance(i, sm);
    for (int i = 1; i < n; i++)
    {
        if(i == sm) continue;
        if(a[0][sm] + a[sm][i] == a[0][i])
        {
            if(a[sm][i] < a[0][sm]) stype[i] = 1, location[i] = sc - a[i][sm], col[i] = true;
            else fp.ad(MP(a[sm][i], i));
        }
    }
    sort(fp.begin(), fp.end());
    col[0] = col[sm] = 1;
    int ss = 0;
    for(auto p : fp)
    {
        int d = getDistance(ss, p.sc);
        int mx = ss;
        for (int i = 0; i < n; i++){
            if(col[i] && location[i] < d + location[ss] && stype[i] == 1)
            {
                if(location[mx] < location[i]) mx = i;
            }}
        if(d - location[mx] + location[ss] + a[mx][sm] == a[sm][p.sc])
        {
            stype[p.sc] = 2;
            location[p.sc] = d + location[ss];
            col[p.sc] = 1;
        }
        else
        {
            stype[p.sc] = 1;
            location[p.sc] = sc - a[sm][p.sc];
            col[p.sc] = 1;
            ss = p.sc;
        }
    }
    fp.clear();
    for (int i = 1; i < n; i++)
    {
        if(i == sm) continue;
        if(a[0][sm] + a[sm][i] != a[0][i])
        {
            fp.ad(MP(a[sm][i], i));
        }
    }
    sort(fp.begin(), fp.end());
    ss = sm;
    for(auto p : fp)
    {
        int d = getDistance(ss, p.sc);
        int mx = ss;
        for (int i = 0; i < n; i++)
        {
            if(col[i] && location[i] > location[ss] - d && stype[i] == 2)
            {
                if(location[mx] > location[i]) mx = i;
            }
        }
        if(d - location[ss] + location[mx] + a[0][mx] == a[0][p.sc])
        {
            stype[p.sc] = 1;
            location[p.sc] = location[ss] - d;
            col[p.sc] = 1;
        }
        else
        {
            stype[p.sc] = 2;
            location[p.sc] = location[0] + a[0][p.sc];
            col[p.sc] = 1;
            ss = p.sc;
        }
    }
    return;
}

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