oj.uz

Submission #107047

# Submission time Handle Problem Language Result Execution time Memory
107047 2019-04-21T14:37:36 Z popovicirobert Towns (IOI15_towns) C++14
0 / 100
 24 ms 512 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) {

    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});
        }*/

        int cur = (get(x, y) + get(x, i) - get(y, i)) / 2;
        R = min(R, max(cur, get(x, y) - cur));

    }

    /*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 = leaves[i][0];
            cnt = 1;

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

            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 && pref[i - 1] <= N / 2 && N - pref[i] <= N / 2) {
            sign = 1;
        }

    }

    return R * sign;*/

    return R;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:23:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 384 KB Output isn't correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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