oj.uz

Submission #282575

# Submission time Handle Problem Language Result Execution time Memory
282575 2020-08-24T15:12:36 Z Kastanda Rail (IOI14_rail) C++11
100 / 100
 157 ms 98656 KB 
// M
#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
const int N = 5005;
int n, D[N][N];
int Dist(int i, int j)
{
        if (D[i][j] == -1)
        {
                if (D[j][i] == -1)
                        D[i][j] = D[j][i] = getDistance(i, j);
                D[i][j] = D[j][i];
        }
        return D[i][j];
}
void findLocation(int _n, int loc0, int location[], int stype[])
{
        n = _n;
        location[0] = loc0;
        stype[0] = 1;
        memset(D, -1, sizeof(D));
        for (int i = 0; i < n; i ++)
                D[i][i] = 0;

        int nw = 1;
        for (int i = 1; i < n; i ++)
                if (Dist(0, i) < Dist(0, nw))
                        nw = i;

        location[nw] = location[0] + Dist(0, nw);
        stype[nw] = 2;

        vector < int > L, R;
        for (int i = 1; i < n; i ++)
                if (i != nw && Dist(0, nw) + Dist(nw, i) == Dist(0, i))
                        L.push_back(i);
                else if (i != nw)
                        R.push_back(i);
        L.push_back(0);
        sort(L.begin(), L.end(), [&](int i, int j){return Dist(nw, i) < Dist(nw, j);});

        vector < int > vec;
        for (int i : L)
        {
                if (!vec.size())
                {
                        stype[i] = 1;
                        location[i] = location[nw] - Dist(nw, i);
                        vec.push_back(i);
                        continue;
                }
                int loc = location[vec.back()] + Dist(vec.back(), i);
                if (loc < location[nw])
                {
                        int le = -1, ri = (int)vec.size() - 1, md;
                        while (ri - le > 1)
                        {
                                md = (le + ri) >> 1;
                                if (location[vec[md]] <= loc)
                                        ri = md;
                                else
                                        le = md;
                        }
                        if (location[vec[ri]] < loc && Dist(nw, vec[ri]) + loc - location[vec[ri]] == Dist(nw, i))
                        {
                                stype[i] = 2;
                                location[i] = loc;
                                continue;
                        }
                }
                stype[i] = 1;
                location[i] = location[nw] - Dist(nw, i);
                vec.push_back(i);
        }

        int st = L[0];
        for (int i : R)
                D[st][i] = D[i][st] = Dist(nw, i) - Dist(nw, st);
        sort(R.begin(), R.end(), [&](int i, int j){return Dist(st, i) < Dist(st, j);});
        vec.clear();
        for (int i : R)
        {
                if (!vec.size())
                {
                        stype[i] = 2;
                        location[i] = location[st] + Dist(st, i);
                        vec.push_back(i);
                        continue;
                }
                int loc = location[vec.back()] - Dist(vec.back(), i);
                if (loc > location[st])
                {
                        int le = -1, ri = (int)vec.size() - 1, md;
                        while (ri - le > 1)
                        {
                                md = (le + ri) >> 1;
                                if (location[vec[md]] >= loc)
                                        ri = md;
                                else
                                        le = md;
                        }
                        if (location[vec[ri]] > loc && Dist(st, vec[ri]) + location[vec[ri]] - loc == Dist(st, i))
                        {
                                stype[i] = 1;
                                location[i] = loc;
                                continue;
                        }
                }
                stype[i] = 2;
                location[i] = location[st] + Dist(st, i);
                vec.push_back(i);
        }
        return ;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98424 KB Output is correct
2 Correct 52 ms 98424 KB Output is correct
3 Correct 53 ms 98296 KB Output is correct
4 Correct 52 ms 98424 KB Output is correct
5 Correct 51 ms 98296 KB Output is correct
6 Correct 52 ms 98424 KB Output is correct
7 Correct 52 ms 98424 KB Output is correct
8 Correct 51 ms 98296 KB Output is correct
9 Correct 51 ms 98296 KB Output is correct
10 Correct 52 ms 98424 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98296 KB Output is correct
2 Correct 53 ms 98296 KB Output is correct
3 Correct 51 ms 98364 KB Output is correct
4 Correct 63 ms 98296 KB Output is correct
5 Correct 60 ms 98424 KB Output is correct
6 Correct 52 ms 98296 KB Output is correct
7 Correct 54 ms 98424 KB Output is correct
8 Correct 52 ms 98296 KB Output is correct
9 Correct 56 ms 98424 KB Output is correct
10 Correct 51 ms 98424 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 98508 KB Output is correct
2 Correct 157 ms 98556 KB Output is correct
3 Correct 135 ms 98552 KB Output is correct
4 Correct 135 ms 98552 KB Output is correct
5 Correct 157 ms 98656 KB Output is correct
6 Correct 149 ms 98552 KB Output is correct
7 Correct 153 ms 98552 KB Output is correct
8 Correct 139 ms 98552 KB Output is correct
9 Correct 138 ms 98552 KB Output is correct
10 Correct 139 ms 98552 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 98520 KB Output is correct
2 Correct 144 ms 98552 KB Output is correct
3 Correct 137 ms 98492 KB Output is correct
4 Correct 139 ms 98524 KB Output is correct
5 Correct 139 ms 98552 KB Output is correct
6 Correct 146 ms 98520 KB Output is correct
7 Correct 142 ms 98552 KB Output is correct
8 Correct 144 ms 98564 KB Output is correct
9 Correct 142 ms 98564 KB Output is correct
10 Correct 136 ms 98564 KB Output is correct
11 Correct 139 ms 98572 KB Output is correct
12 Correct 137 ms 98568 KB Output is correct
13 Correct 140 ms 98572 KB Output is correct
14 Correct 146 ms 98564 KB Output is correct
15 Correct 137 ms 98564 KB Output is correct
16 Correct 140 ms 98552 KB Output is correct
17 Correct 139 ms 98552 KB Output is correct
18 Correct 142 ms 98552 KB Output is correct
19 Correct 139 ms 98552 KB Output is correct
20 Correct 141 ms 98612 KB Output is correct