oj.uz

Submission #773971

# Submission time Handle Problem Language Result Execution time Memory
773971 2023-07-05T10:09:07 Z boris_mihov Rail (IOI14_rail) C++17
30 / 100
 45 ms 524 KB 
#include "rail.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n;
int distA[MAXN];
int distB[MAXN];
int myDist(int u, int v)
{
    return getDistance(u - 1, v - 1);
}

void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    for (int i = 2 ; i <= n ; ++i)
    {
        distA[i] = myDist(1, i);
    }

    location[0] = first;
    stype[0] = 1;

    int minIdx = 2;
    for (int i = 3 ; i <= n ; ++i)
    {
        assert(distA[i] != distA[minIdx]);
        if (distA[i] < distA[minIdx])
        {
            minIdx = i;
        }
    }

    location[minIdx - 1] = first + distA[minIdx];
    stype[minIdx - 1] = 2;

    for (int i = 2 ; i <= n ; ++i)
    {
        if (i == minIdx)
        {
            continue;
        }

        distB[i] = myDist(minIdx, i);
    }

    for (int i = 2 ; i <= n ; ++i)
    {
        if (i == minIdx)
        {
            continue;
        }

        if (distA[i] == distB[i] + location[minIdx - 1] - location[0])
        {
            stype[i - 1] = 1;
            location[i - 1] = location[minIdx - 1] - distB[i];
        }

        if (distB[i] == distA[i] + location[minIdx - 1] - location[0])
        {
            stype[i - 1] = 2;
            location[i - 1] = distA[i] + location[0];
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 524 KB Output isn't correct
2 Halted 0 ms 0 KB -