Submission #434026

#	Time	Username	Problem	Language	Result	Execution time	Memory
434026		79brue	Towns (IOI15_towns)	C++14	100 / 100	26 ms	884 KiB

towns

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

using namespace std;

typedef long long ll;

int n, k;
int x, y, len;
int a[120], b[120];

vector<int> dist;
map<int, int> idx;

int branch[120], loc[120];
vector<int> vec[120];
int maxB[120];
int cnt[120];

int R=1e9, C;
bool twoC;

bool sameSubtree(int x, int y){
    return getDistance(x, y) < branch[x] + branch[y];
}

int hubDistance(int N, int sub){
    dist.clear();
    idx.clear();
    for(int i=0; i<120; i++) vec[i].clear();
    memset(branch, 0, sizeof(branch));
    memset(loc, 0, sizeof(loc));
    memset(maxB, 0, sizeof(maxB));
    memset(cnt, 0, sizeof(cnt));
    R = 1e9;
    twoC = 0;

	n = N;
	x = 0;
	for(int i=0; i<n; i++){
        if(i!=x) a[i] = getDistance(x, i);
	}
	y = max_element(a, a+n) - a;
	len = a[y];
	for(int i=0; i<n; i++){
        if(i==x) b[i] = len;
        else if(i!=y) b[i] = getDistance(y, i);
	}

    dist.push_back(0);
    dist.push_back(len);
	for(int i=0; i<n; i++){
        if(i==x || i==y) continue;
        branch[i] = (a[i] + b[i] - len) / 2;
        dist.push_back(a[i] - branch[i]);
	}

	sort(dist.begin(), dist.end());
	dist.erase(unique(dist.begin(), dist.end()), dist.end());
	for(int i=0; i<(int)dist.size(); i++){
        idx[dist[i]] = i;
	}

    int k = (int)dist.size();
    for(int i=0; i<n; i++){
        loc[i] = idx[a[i] - branch[i]];
        cnt[loc[i]]++;
        vec[loc[i]].push_back(i);
        maxB[loc[i]] = max(maxB[loc[i]], branch[i]);
    }

    for(int i=1; i<k-1; i++){
        int maxLen = -1;
        for(int j=0; j<k; j++){
            maxLen = max(maxLen, abs(dist[i] - dist[j]) + maxB[j]);
        }
        if(maxLen < R){
            R = maxLen;
            C = i;
            twoC = 0;
        }
        else if(maxLen == R) twoC = 1;
    }

    if(twoC){
        int A = accumulate(cnt, cnt+C+1, 0);
        int B = accumulate(cnt+C+1, cnt+k, 0);
        if(A == B) return R;
        if(A < B) C++;
    }

    if(accumulate(cnt, cnt+C, 0) > n/2) return -R;
    if(accumulate(cnt+C+1, cnt+k, 0) > n/2) return -R;
    if(cnt[C] <= n/2) return R;

    vector<pair<vector<int>, vector<int> > > res;
    stack<int> stk;
    vector<int> cand = vec[C];

    vector<int> vA, vB;
    for(int i=0; i<(int)cand.size(); i++){
        if(stk.empty() || sameSubtree(stk.top(), cand[i])){
            stk.push(cand[i]);
            vA.push_back(cand[i]);
            continue;
        }
        else{
            vB.push_back(cand[i]);
            stk.pop();

            if(stk.empty()){
                res.push_back(make_pair(vA, vB));
                vA.clear();
                vB.clear();
            }
            continue;
        }
    }

    if(stk.empty()) return R;
    int tcnt = vA.size();
    int key = vA.back();

    for(auto p: res){
        vA = p.first, vB = p.second;
        if(sameSubtree(vA.back(), key)) tcnt += (int)vA.size();
        else{
            for(auto x: vB) tcnt += sameSubtree(x, key);
        }
    }

    if(tcnt <= n/2) return R;
    return -R;
}

Compilation message (stderr)

towns.cpp: In function 'bool sameSubtree(int, int)':
towns.cpp:23:29: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   23 | bool sameSubtree(int x, int y){
      |                         ~~~~^
towns.cpp:9:8: note: shadowed declaration is here
    9 | int x, y, len;
      |        ^
towns.cpp:23:22: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   23 | bool sameSubtree(int x, int y){
      |                  ~~~~^
towns.cpp:9:5: note: shadowed declaration is here
    9 | int x, y, len;
      |     ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:43:26: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   43 |  y = max_element(a, a+n) - a;
      |      ~~~~~~~~~~~~~~~~~~~~^~~
towns.cpp:64:9: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   64 |     int k = (int)dist.size();
      |         ^
towns.cpp:8:8: note: shadowed declaration is here
    8 | int n, k;
      |        ^
towns.cpp:121:23: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  121 |     int tcnt = vA.size();
      |                ~~~~~~~^~
towns.cpp:128:22: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  128 |             for(auto x: vB) tcnt += sameSubtree(x, key);
      |                      ^
towns.cpp:9:5: note: shadowed declaration is here
    9 | int x, y, len;
      |     ^
towns.cpp:27:28: warning: unused parameter 'sub' [-Wunused-parameter]
   27 | int hubDistance(int N, int sub){
      |                        ~~~~^~~

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