oj.uz

Submission #46529

# Submission time Handle Problem Language Result Execution time Memory
46529 2018-04-21T09:54:53 Z RayaBurong25_1 Rail (IOI14_rail) C++17
100 / 100
 243 ms 99152 KB 
#include "rail.h"
#include <set>
#include <cassert>
#define INF 1000000007
int Dist[5005][5005];
bool operator<(std::pair<int, int> a, std::pair<int, int> b)
{
    return (a.first < b.first || (a.first == b.first && a.second < b.second));
}
void findLocation(int N, int first, int location[], int stype[])
{
    int i, j;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (i == j)
                Dist[i][j] = 0;
            else
                Dist[i][j] = -1;
        }
    }
    location[0] = first;
    stype[0] = 1;
    int u, ud = INF;
    for (i = 0; i < N; i++)
    {
        if (Dist[0][i] == -1)
        {
            Dist[0][i] = getDistance(0, i);
            Dist[i][0] = Dist[0][i];
            if (Dist[0][i] < ud)
            {
                u = i;
                ud = Dist[0][i];
            }
        }
    }
    if (ud == INF)
        return;
    location[u] = first + ud;
    stype[u] = 2;
    for (i = 0; i < N; i++)
    {
        if (Dist[u][i] == -1)
        {
            Dist[u][i] = getDistance(u, i);
            Dist[i][u] = Dist[u][i];
            if (Dist[u][i] < Dist[u][0] && Dist[u][i] == Dist[0][i] - Dist[0][u])
            {
                location[i] = location[u] - Dist[u][i];
                stype[i] = 1;
            }
        }
    }
    // for (i = 0; i < N; i++)
    //     printf("i%d #%d %d\n", i, stype[i], location[i]);
    // printf("u%d\n", u);
    int v, d;
    std::set<std::pair<int, int> > M;
    std::set<int> C;
    M.clear();
    C.clear();
    v = 0;
    C.insert(location[0]);
    for (i = 0; i < N; i++)
    {
        if (stype[i] != 0) continue;
        if (Dist[0][i] != Dist[0][u] + Dist[u][i]) continue;
        M.insert({Dist[u][i], i});
    }
    std::set<std::pair<int, int> >::iterator it;
    for (it = M.begin(); it != M.end(); it++)
    {
        if (Dist[v][it->second] == -1)
        {
            Dist[v][it->second] = getDistance(v, it->second);
            Dist[it->second][v] = Dist[v][it->second];
        }
        d = (Dist[u][v] + Dist[v][it->second] - Dist[u][it->second])/2;
        // printf("it (%d %d) d %d -> find %d\n", it->first, it->second, d, location[v] + d);
        if (C.find(location[v] + d) != C.end())
        {
            location[it->second] = location[v] + Dist[v][it->second];
            stype[it->second] = 2;
        }
        else
        {
            location[it->second] = location[u] - Dist[u][it->second];
            stype[it->second] = 1;
            C.insert(location[it->second]);
            v = it->second;
        }
    }
    // for (i = 0; i < N; i++)
    //     printf("i%d #%d %d\n", i, stype[i], location[i]);
    M.clear();
    C.clear();
    v = u;
    C.insert(location[u]);
    for (i = 0; i < N; i++)
    {
        if (stype[i] != 0) continue;
        M.insert({Dist[0][i], i});
    }
    for (it = M.begin(); it != M.end(); it++)
    {
        if (Dist[v][it->second] == -1)
        {
            Dist[v][it->second] = getDistance(v, it->second);
            Dist[it->second][v] = Dist[v][it->second];
        }
        d = (Dist[0][v] + Dist[v][it->second] - Dist[0][it->second])/2;
        if (C.find(location[v] - d) != C.end())
        {
            location[it->second] = location[v] - Dist[v][it->second];
            stype[it->second] = 1;
        }
        else
        {
            location[it->second] = location[0] + Dist[0][it->second];
            stype[it->second] = 2;
            C.insert(location[it->second]);
            v = it->second;
        }
    }
    for (i = 0; i < N; i++)
        assert(stype[i] != 0);
    // for (i = 0; i < N; i++)
    //     printf("i%d #%d %d\n", i, stype[i], location[i]);
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:80:23: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
         d = (Dist[u][v] + Dist[v][it->second] - Dist[u][it->second])/2;
              ~~~~~~~~~^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 788 KB Output is correct
2 Correct 2 ms 884 KB Output is correct
3 Correct 2 ms 884 KB Output is correct
4 Correct 3 ms 884 KB Output is correct
5 Correct 2 ms 884 KB Output is correct
6 Correct 3 ms 904 KB Output is correct
7 Correct 3 ms 904 KB Output is correct
8 Correct 2 ms 904 KB Output is correct
9 Correct 2 ms 920 KB Output is correct
10 Correct 3 ms 1048 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 98944 KB Output is correct
2 Correct 183 ms 98944 KB Output is correct
3 Correct 169 ms 98944 KB Output is correct
4 Correct 195 ms 98944 KB Output is correct
5 Correct 164 ms 98944 KB Output is correct
6 Correct 175 ms 99036 KB Output is correct
7 Correct 184 ms 99036 KB Output is correct
8 Correct 192 ms 99036 KB Output is correct
9 Correct 228 ms 99036 KB Output is correct
10 Correct 227 ms 99036 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 99036 KB Output is correct
2 Correct 161 ms 99036 KB Output is correct
3 Correct 159 ms 99036 KB Output is correct
4 Correct 164 ms 99036 KB Output is correct
5 Correct 196 ms 99036 KB Output is correct
6 Correct 162 ms 99152 KB Output is correct
7 Correct 175 ms 99152 KB Output is correct
8 Correct 174 ms 99152 KB Output is correct
9 Correct 194 ms 99152 KB Output is correct
10 Correct 190 ms 99152 KB Output is correct
11 Correct 176 ms 99152 KB Output is correct
12 Correct 169 ms 99152 KB Output is correct
13 Correct 176 ms 99152 KB Output is correct
14 Correct 179 ms 99152 KB Output is correct
15 Correct 188 ms 99152 KB Output is correct
16 Correct 176 ms 99152 KB Output is correct
17 Correct 243 ms 99152 KB Output is correct
18 Correct 174 ms 99152 KB Output is correct
19 Correct 224 ms 99152 KB Output is correct
20 Correct 223 ms 99152 KB Output is correct