oj.uz

Submission #778287

# Submission time Handle Problem Language Result Execution time Memory
778287 2023-07-10T08:13:55 Z boris_mihov Towns (IOI15_towns) C++17
25 / 100
 16 ms 1100 KB 
#include "towns.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 query(int u, int v)
{
    return getDistance(u - 1, v - 1);
}

int distA[MAXN];
int distB[MAXN];
int distC[MAXN];
int hubDistance(int n, int sub) 
{
    int max = 0;
    int dist = 0;
    for (int i = 2 ; i <= n ; ++i)
    {
        distA[i] = query(1, i);
        if (distA[i] > dist)
        {
            max = i;
            dist = distA[i];
        }
    }

    dist = 0;
    int end = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        distB[i] = query(max, i);
        if (distB[i] > dist)
        {
            end = i;
            dist = distB[i];
        }
    }

    int diff = INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        distC[i] = query(i, end);
        diff = std::min(diff, abs(distB[i] - distC[i]));
    }

    return (distB[end] + diff) / 2;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:20:28: warning: unused parameter 'sub' [-Wunused-parameter]
   20 | int hubDistance(int n, int sub)
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 864 KB Output is correct
2 Correct 9 ms 708 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 13 ms 852 KB Output is correct
5 Correct 12 ms 832 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 840 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 15 ms 980 KB Output is correct
4 Correct 13 ms 852 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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