oj.uz

Submission #434026

# Submission time Handle Problem Language Result Execution time Memory
434026 2021-06-20T14:12:11 Z 79brue Towns (IOI15_towns) C++14
100 / 100
 26 ms 884 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 332 KB Output is correct
2 Correct 13 ms 360 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 18 ms 332 KB Output is correct
5 Correct 20 ms 452 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 352 KB Output is correct
2 Correct 17 ms 348 KB Output is correct
3 Correct 19 ms 332 KB Output is correct
4 Correct 20 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 352 KB Output is correct
2 Correct 20 ms 840 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 19 ms 864 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 356 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 332 KB Output is correct
2 Correct 26 ms 824 KB Output is correct
3 Correct 19 ms 884 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 472 KB Output is correct
2 Correct 19 ms 840 KB Output is correct
3 Correct 19 ms 844 KB Output is correct