Submission #930643

#	Time	Username	Problem	Language	Result	Execution time	Memory
930643		Der_Vlapos	Rail (IOI14_rail)	C++17	30 / 100	741 ms	262144 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<pii> getAllDists(int v, vector<int> els)
// {
//     vector<pii> res;
//     for (auto el : els)
//         res.pb({getDistance(v, el), el});

//     return res;
// }

// pii doStuff(int v, int T)
// {
//     vector<pii> vals;
//     {
//         vector<int> bf;
//         for (int i = 0; i < n; ++i)
//             if (!tp[i])
//                 bf.pb(i);
//         vals = getAllDists(v, bf);
//         sort(vals.begin(), vals.end());
//     }

//     if (vals.size() == 0)
//         return {-1, -1};

//     int curClosing = vals[0].s;
//     int curD = vals[0].f;
//     tp[curClosing] = 2 - T;
//     loc[curClosing] = (T ? loc[v] - vals[0].f : loc[v] + vals[0].f);
//     for (int i = 1; i < vals.size(); ++i)
//     {
//         if (vals[i].f > getDistance(curClosing, vals[i].s))
//             break;
//         curClosing = vals[i].s;
//         curD = vals[i].f;
//         tp[curClosing] = 2 - T;
//         loc[curClosing] = (T ? loc[v] - vals[i].f : loc[v] + vals[i].f);
//     }

//     return {curClosing, curD};
// }

vector<vector<int>> dists;
vector<int> loc, tp;
int n;

map<pii, int> was;

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

    for (int i = 0; i < vals.size(); ++i)
    {
        if (!tp[vals[i].s] and (pr == -1 or dists[pr][vals[i].s] > dists[v][vals[i].s]))
        {
            int to = vals[i].s;
            tp[to] = 2 - T;
            loc[to] = (T ? loc[v] - vals[i].f : loc[v] + vals[i].f);
            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));
    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:73: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]
   73 |     for (int i = 0; i < vals.size(); ++i)
      |                     ~~^~~~~~~~~~~~~

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