Submission #930671

#	Time	Username	Problem	Language	Result	Execution time	Memory
930671		Der_Vlapos	Rail (IOI14_rail)	C++17	56 / 100	1921 ms	168332 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()

vector<vector<int>> dists;
vector<int> loc, tp, shortest;
int n;
int C = 0;

void mark(int v, int pr, int T)
{
    assert(tp[v]);
    vector<pii> vals;
    for (int i = 0; i < n; ++i)
        if (!tp[i])
        {
            assert(!dists[v][i] and !dists[i][v]);
            int toD = getDistance(v, i);
            C++;
            assert(C <= (n) * (n - 1) / 2);
            shortest[i] = min(shortest[i], toD);
            dists[v][i] = toD;
            vals.pb({toD, i});
        }
    sort(all(vals));

    for (int i = 0; i < vals.size(); ++i)
    {
        int to = vals[i].s;
        if (!tp[to] and (pr == -1 or dists[v][to] == shortest[to]))
        {
            tp[to] = 2 - T;
            loc[to] = (T ? loc[v] - vals[i].f : loc[v] + vals[i].f);
            // cout << v << " -> " << to << "!\n";
            mark(to, v, 1 - T);
        }
    }
}

void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    loc.resize(N);
    tp.resize(N);
    dists.resize(N, vector<int>(N));
    shortest.resize(N, 2e9 + 10);
    loc[0] = first;
    tp[0] = 1;

    mark(0, -1, 0);

    for (int i = 0; i < n; ++i)
    {
        location[i] = loc[i];
        stype[i] = tp[i];
        // cout << stype[i] << " " << location[i] << " " << i << "!\n";
    }
}

// /* This is sample grader for the contestant */

// #include <unistd.h>
// #include <stdlib.h>
// #include <stdio.h>
// #include <string.h>
// #include <assert.h>
// #include "rail.h"

// typedef struct Station
// {
//     int index;
//     int type;
//     int location;
//     int L, R;
// } STATION;
// long long cnt;
// static int S, SUBTASK;
// static STATION stations[10004];

// int cmp_fun_1(const void *a, const void *b)
// {
//     STATION c, d;
//     c = *(STATION *)(a);
//     d = *(STATION *)(b);
//     return c.location < d.location ? -1 : 1;
// }

// int cmp_fun_2(const void *a, const void *b)
// {
//     STATION c, d;
//     c = *(STATION *)(a);
//     d = *(STATION *)(b);
//     return c.index < d.index ? -1 : 1;
// }

// void now_I_want_to_getLR()
// {
//     int now = stations[S - 1].index, i;
//     for (i = S - 2; i >= 0; i--)
//     {
//         stations[i].R = now;
//         if (stations[i].type == 2)
//             now = stations[i].index;
//     }
//     now = stations[0].index;
//     for (i = 1; i < S; i++)
//     {
//         stations[i].L = now;
//         if (stations[i].type == 1)
//             now = stations[i].index;
//     }
// }

// int getDistance(int x, int y)
// {
//     cnt++;
//     if (x == y)
//         return 0;
//     if (x < 0 || x >= S || y < 0 || y >= S)
//         return -1;
//     if (stations[x].location > stations[y].location)
//     {
//         int tmp = x;
//         x = y;
//         y = tmp;
//     }
//     int ret = 0;
//     if (stations[x].type == 1 && stations[y].type == 1)
//     {
//         ret = stations[stations[y].R].location - stations[x].location + stations[stations[y].R].location - stations[y].location;
//     }
//     else if (stations[x].type == 1 && stations[y].type == 2)
//     {
//         ret = stations[y].location - stations[x].location;
//     }
//     else if (stations[x].type == 2 && stations[y].type == 2)
//     {
//         ret = stations[x].location - stations[stations[x].L].location + stations[y].location - stations[stations[x].L].location;
//     }
//     else if (stations[x].type == 2 && stations[y].type == 1)
//     {
//         ret = stations[x].location - stations[stations[x].L].location + stations[stations[y].R].location - stations[stations[x].L].location + stations[stations[y].R].location - stations[y].location;
//     }
//     return ret;
// }

// void getInput()
// {
//     int g;
//     g = scanf("%d", &SUBTASK);
//     g = scanf("%d", &S);
//     int s;
//     for (s = 0; s < S; s++)
//     {
//         int type, location;
//         g = scanf(" %d %d", &type, &location);
//         stations[s].index = s;
//         stations[s].location = location;
//         stations[s].type = type;
//         stations[s].L = -1;
//         stations[s].R = -1;
//     }
//     qsort(stations, S, sizeof(STATION), cmp_fun_1);
//     now_I_want_to_getLR();
//     qsort(stations, S, sizeof(STATION), cmp_fun_2);
// }

// int serverGetStationNumber()
// {
//     return S;
// }

// int serverGetSubtaskNumber()
// {
//     return SUBTASK;
// }

// int serverGetFirstStationLocation()
// {
//     return stations[0].location;
// }

// int main()
// {
//     int i;
//     getInput();
//     cnt = 0;

//     int location[10005];
//     int type[10005];
//     int ok = 1;
//     findLocation(S, serverGetFirstStationLocation(), location, type);
//     if (SUBTASK == 3 && cnt > S * (S - 1))
//         ok = 0;
//     if (SUBTASK == 4 && cnt > 3 * (S - 1))
//         ok = 0;

//     for (i = 0; i < S; i++)
//         if (type[i] != stations[i].type || location[i] != stations[i].location)
//             ok = 0;
//     if (ok == 0)
//         printf("Incorrect");
//     else
//         printf("Correct");
//     return 0;
// }

Compilation message (stderr)

rail.cpp: In function 'void mark(int, int, int)':
rail.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < vals.size(); ++i)
      |                     ~~^~~~~~~~~~~~~

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