oj.uz

Submission #107066

# Submission time Handle Problem Language Result Execution time Memory
107066 2019-04-21T16:21:26 Z popovicirobert Towns (IOI15_towns) C++14
61 / 100
 32 ms 468 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = (int) 1e9 + 5;

map < pair <int, int>, int > mp;

inline int get(int x, int y) {
    if(x > y) {
        swap(x, y);
    }
    if(x == y) {
        return 0;
    }
    if(mp[{x, y}] != 0) {
        return mp[{x, y}];
    }
    return mp[{x, y}] = getDistance(x, y);
}

int hubDistance(int N, int sub) {

    mp.clear();
    int i;

    int x = 0;
    for(i = 1; i < N; i++) {
        if(get(0, i) > get(0, x)) {
            x = i;
        }
    }

    int y = 0;
    for(i = 1; i < N; i++) {
        if(get(x, i) > get(x, y)) {
            y = i;
        }
    }

    vector < pair <int, int> > arr;
    int R = INF;

    for(i = 0; i < N; i++) {
        int cur = (get(x, i) + get(x, 0) - get(i, 0)) / 2;

        if(cur <= (get(x, 0) + get(x, y) - get(0, y)) / 2) {
            R = min(R, max(cur, get(x, y) - cur));
            arr.push_back({cur, i});
        }
    }

    if(sub < 3) {
        return R;
    }

    sort(arr.begin(), arr.end());

    vector < vector <int> > leaves(N + 1);
    vector <int> len(N + 1);

    int sz = 0;
    for(i = 0; i < arr.size(); i++) {
        if(i > 0 && arr[i].first != arr[i - 1].first) {
            sz++;
        }
        leaves[sz].push_back(arr[i].second);
        len[sz] = arr[i].first;
    }

    leaves[1].push_back(leaves[0].back());
    leaves[0].clear();

    if(y == 0) {
        leaves[sz - 1].push_back(0);
        leaves[sz].clear();
        sz--;
    }

    vector <int> pref(sz + 2);
    for(i = 1; i <= sz; i++) {
        pref[i] = pref[i - 1] + leaves[i].size();
    }

    int sign = -1;

    for(i = 1; i <= sz; i++) {
        if(max(len[i], get(x, y) - len[i]) != R) {
            continue;
        }

        int cnt = 0;

        if(leaves[i].size() > N / 2) {

            int nod;
            for(int j = 0; j < leaves[i].size(); j++) {
                int cur = leaves[i][j];

                if(cnt == 0) {
                    nod = cur;
                }

                if(len[i] < (get(nod, x) + get(cur, x) - get(nod, cur)) / 2) {
                    cnt++;
                }
                else {
                    cnt--;
                }
            }

            cnt = 0;
            for(int j = 0; j < leaves[i].size(); j++) {
                int cur = leaves[i][j];
                if(len[i] < (get(nod, x) + get(cur, x) - get(nod, cur)) / 2) {
                    cnt++;
                }
            }

        }

        if(cnt <= N / 2 && max(pref[i - 1], N - pref[i]) <= N / 2) {
            sign = 1;
        }

    }

    return R * sign;

}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < arr.size(); i++) {
                ~~^~~~~~~~~~~~
towns.cpp:83:31: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         pref[i] = pref[i - 1] + leaves[i].size();
towns.cpp:95:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(leaves[i].size() > N / 2) {
            ~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:98:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < leaves[i].size(); j++) {
                            ~~^~~~~~~~~~~~~~~~~~
towns.cpp:114:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < leaves[i].size(); j++) {
                            ~~^~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 384 KB Output is correct
2 Correct 27 ms 384 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 25 ms 384 KB Output is correct
5 Correct 21 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 17 ms 384 KB Output is correct
3 Correct 18 ms 384 KB Output is correct
4 Correct 19 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Correct 32 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 22 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 25 ms 468 KB Output is correct
3 Correct 21 ms 384 KB Output is correct

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 384 KB Output is correct
2 Incorrect 4 ms 436 KB Output isn't correct
3 Halted 0 ms 0 KB -