Submission #930670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930670	2024-02-20T09:14:29 Z	Der_Vlapos	Rail (IOI14_rail)	C++17	Compilation error	0 ms	0 KB

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

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)
      |                     ~~^~~~~~~~~~~~~
rail.cpp: In function 'void getInput()':
rail.cpp:156:9: warning: variable 'g' set but not used [-Wunused-but-set-variable]
  156 |     int g;
      |         ^
/usr/bin/ld: /tmp/ccsoR7u7.o: in function `getDistance':
grader.cpp:(.text+0x0): multiple definition of `getDistance'; /tmp/cc8K3Ag8.o:rail.cpp:(.text+0x590): first defined here
/usr/bin/ld: /tmp/ccsoR7u7.o:(.bss+0x0): multiple definition of `cnt'; /tmp/cc8K3Ag8.o:(.bss+0x0): first defined here
/usr/bin/ld: /tmp/ccsoR7u7.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc8K3Ag8.o:rail.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status