Submission #434077

#	Time	Username	Problem	Language	Result	Execution time	Memory
434077		benedict0724	Towns (IOI15_towns)	C++17	35 / 100	25 ms	844 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

int S = 0, E;
const int INF = 1e9;
int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110];
vector<pair<int, int>> v;

bool getSame(int x, int y)
{
    if(Hub[x] + Hub[y] > getDistance(x, y)) return true;
    return false;
}

int hubDistance(int N, int sub) {
    v.clear();
    for(int i=0;i<N;i++) dist[i] = dist2[i] = Hub[i] = x[i] = y[i] = 0;
	for(int i=1;i<N;i++) dist[i] = getDistance(S, i);
	E = 1;
	for(int i=1;i<N;i++) if(dist[E] < dist[i]) E = i;
	for(int i=1;i<N;i++)
    {
        if(i == E) continue;
        dist2[i] = getDistance(i, E);
    }

    int Rad = dist[E];
    int opt = INF;
    for(int i=1;i<N;i++)
    {
        if(i == E) continue;
        distD[i] = (dist[i] + dist2[i] - Rad)/2;
        x[i] = (dist[i] + Rad - dist2[i])/2;
        y[i] = (-dist[i] + Rad + dist2[i])/2;
    }
    for(int i=1;i<N;i++)
    {
        if(i == E) continue;
        int M = max(x[i], Rad - x[i]);
        for(int j=1;j<N;j++)
        {
            if(j == E) continue;
            tmp[j] = distD[j] + abs(x[i] - x[j]);
            M = max(M, tmp[j]);
        }
        if(M < opt)
        {
            opt = M;
            Hub[S] = x[i];
            Hub[E] = Rad - x[i];
            for(int j=1;j<N;j++)
            {
                if(j == E) continue;
                Hub[j] = tmp[j];
            }
        }
    }

    int R = 0;
    for(int i=0;i<N;i++) R = max(R, Hub[i]);

    stack<int> st;
    st.push(0);
    int j=0;
    for(int i=1;i<N;i++)
    {
        if(st.empty())
        {
            st.push(i);
            continue;
        }
        int t = st.top();
        if(getSame(t, i)) st.push(i);
        else
        {
            st.pop();
            v.push_back({i, 1});
            if(st.empty())
            {
                v.push_back({t, (i-j+1)/2});
                j = i+1;
            }
        }
    }
    if(st.empty()) return R;
    int t = st.top();
    int cnt = (N - j + st.size())/2;
    for(auto i : v)
    {
        if(getSame(i.first, t)) cnt += i.second;
    }

    if(cnt > N/2) return -R;
    return R;
}

Compilation message (stderr)

towns.cpp: In function 'bool getSame(int, int)':
towns.cpp:11:25: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   11 | bool getSame(int x, int y)
      |                     ~~~~^
towns.cpp:8:68: note: shadowed declaration is here
    8 | int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110];
      |                                                                    ^
towns.cpp:11:18: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   11 | bool getSame(int x, int y)
      |              ~~~~^
towns.cpp:8:60: note: shadowed declaration is here
    8 | int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110];
      |                                                            ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:89:34: warning: conversion from 'std::stack<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   89 |     int cnt = (N - j + st.size())/2;
      |               ~~~~~~~~~~~~~~~~~~~^~
towns.cpp:17:28: warning: unused parameter 'sub' [-Wunused-parameter]
   17 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39