oj.uz

답안 #930671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930671 2024-02-20T09:14:49 Z Der_Vlapos 철로 (IOI14_rail) C++17
56 / 100
 1921 ms 168332 KB 
#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)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 516 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1669 ms 161560 KB Output is correct
2 Correct 1671 ms 154040 KB Output is correct
3 Correct 1695 ms 147336 KB Output is correct
4 Correct 1753 ms 145172 KB Output is correct
5 Correct 1695 ms 149516 KB Output is correct
6 Correct 1745 ms 168332 KB Output is correct
7 Correct 1767 ms 160228 KB Output is correct
8 Correct 1681 ms 144528 KB Output is correct
9 Correct 1707 ms 136172 KB Output is correct
10 Correct 1697 ms 135120 KB Output is correct

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1673 ms 161596 KB Output is correct
2 Correct 1813 ms 154104 KB Output is correct
3 Correct 1746 ms 147244 KB Output is correct
4 Correct 1693 ms 145468 KB Output is correct
5 Correct 1748 ms 149476 KB Output is correct
6 Correct 1687 ms 168276 KB Output is correct
7 Correct 1737 ms 160348 KB Output is correct
8 Correct 1736 ms 144432 KB Output is correct
9 Correct 1921 ms 136276 KB Output is correct
10 Correct 1672 ms 134996 KB Output is correct
11 Incorrect 1791 ms 147392 KB Output isn't correct
12 Halted 0 ms 0 KB -