Submission #286437

#	Time	Username	Problem	Language	Result	Execution time	Memory
286437		AaronNaidu	Towns (IOI15_towns)	C++14	26 / 100	23 ms	1024 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"
using namespace std;

int n;
int dists[111][111];
int maxDists[1000];
int distToRoot[1000];
int lcaHeights[111][111];
int leafCount[1000];
int par[1000];
vector<pair<int, int> > tree[1000];
int pointer;
vector<vector<int> > secretDistances;

/*int getDistance(int i, int j) {
    return secretDistances[i][j];
}*/

void solveRegion(vector<int> leafs, int root, int rootHeight) {
    if (leafs.size() == 0)
    {
        return;
    }
    if (leafs.size() == 1)
    {
        int height = distToRoot[leafs[0]] - rootHeight;
        tree[root].push_back({leafs[0], height});
        tree[leafs[0]].push_back({root, height});
        return;
    }
    vector<int> part1, part2;
    int newRoot = pointer;
    pointer++;
    int newRootHeight = 1000000007;
    int firstInSet = leafs[0];
    part1.push_back(firstInSet);
    for (int i = 1; i < leafs.size(); i++)
    {
        if (lcaHeights[firstInSet][leafs[i]] > rootHeight)
        {
            newRootHeight = min(newRootHeight, lcaHeights[firstInSet][leafs[i]]);
            part1.push_back(leafs[i]);
        }
        else
        {
            part2.push_back(leafs[i]);
        }
    }
    if (newRootHeight == 1000000007)
    {
        newRootHeight = rootHeight;
        newRoot = root;
        pointer--;
    }
    if (part1.size() > 1)
    {
        int newHeight = newRootHeight - rootHeight;
        tree[root].push_back({newRoot, newHeight});
        tree[newRoot].push_back({root, newHeight});
    }
    solveRegion(part1, newRoot, newRootHeight);
    solveRegion(part2, root, rootHeight);
}

int dfs(int node, int parent, int distance, int root) {
    //cout << "DFS on node " << node << "\n";
    par[node] = parent;
    int leafC = 0;
    int maxDist = distance;
    //fullDists[root][node] = distance;
    for (auto i : tree[node])
    {
        if (i.first != parent)
        {
            //cout << "Spot " << i.first << " distance " << i.second << "away\n";
            maxDist = max(maxDist, dfs(i.first, node, distance + i.second, root)); 
            leafC += leafCount[i.first];
        }
    }
    if (tree[node].size() == 1)
    {
        leafC = 1;
    }
    leafCount[node] = leafC;
    //cout << "Exit DFS on node " << node << "\n";
    return maxDist;
}

/*void secret() {
    secretDistances.resize(11);
    for (int i = 0; i < 11; i++)
    {
        secretDistances[i].resize(11);
    }
    secretDistances[0] = {0, 17, 18, 20, 17, 12, 20, 16, 23, 20, 11};
    secretDistances[1] = {17, 0, 23, 25, 22, 17, 25, 21, 28, 25, 16};
    secretDistances[2] = {18, 23, 0, 12, 21, 16, 24, 20, 27, 24, 17};
    secretDistances[3] = {20, 25, 12, 0, 23, 18, 26, 22, 29, 26, 19};
    secretDistances[4] = {17, 22, 21, 23, 0, 9, 21, 17, 26, 23, 16};
    secretDistances[5] = {12, 17, 16, 18, 9, 0, 16, 12, 21, 18, 11};
    secretDistances[6] = {20, 25, 24, 26, 21, 16, 0, 10, 29, 26, 19};
    secretDistances[7] = {16, 21, 20, 22, 17, 12, 10, 0, 25, 22, 15};
    secretDistances[8] = {23, 28, 27, 29, 26, 21, 29, 25, 0, 21, 22};
    secretDistances[9] = {20, 25, 24, 26, 23, 18, 26, 22, 21, 0, 19};
    secretDistances[10] = {11, 16, 17, 19, 16, 11, 19, 15, 22, 19, 0};
}*/

bool isGood(int node) {
    //cout << "Checking " << node << "\n";
    int totSum = 0;
    for (auto i : tree[node])
    {
        if (i.first != par[node])
        {
            if (leafCount[i.first] > n/2)
            {
                return false;
            }
            totSum += leafCount[i.first];
        }
    }
    if (n-totSum > n/2)
    {
        return false;
    }
    return true;
}

int hubDistance(int N, int sub) {
    //secret();
    n = N;
    pointer = 200;
    for (int i = 0; i < 1000; i++)
    {
        tree[i].clear();
        distToRoot[i] = -1;
        maxDists[i] = -1;        
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            dists[i][j] = getDistance(i, j);
            dists[j][i] = dists[i][j];
        }
    }
    for (int i = 1; i < n; i++)
    {
        distToRoot[i] = getDistance(i, 0);
    }
    int minHeight = 1000000007;
    for (int i = 1; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            lcaHeights[i][j] = (distToRoot[i] + distToRoot[j] - dists[i][j])/2; 
            lcaHeights[j][i] = lcaHeights[i][j];
            minHeight = min(minHeight, lcaHeights[i][j]); 
        }
    }
    tree[0].push_back({pointer, minHeight});
    tree[pointer].push_back({0, minHeight});
    pointer++;
    vector<int> s;
    for (int i = 1; i < n; i++)
    {
        s.push_back(i);
    }
    solveRegion(s, pointer-1, minHeight);
    int minMax = 1000000007;
    for (int i = 200; i < pointer; i++)
    {
        maxDists[i] = dfs(i, -1, 0, i);
        minMax = min(maxDists[i],minMax);
    }
    bool hasGoodHub = false;
    for (int i = 200; i < pointer; i++)
    {
        if (maxDists[i] == minMax)
        {
            hasGoodHub |= isGood(i);
        }
    }
    if (hasGoodHub)
    {
        return minMax;
    }    
    return -minMax;
}

Compilation message (stderr)

towns.cpp: In function 'void solveRegion(std::vector<int>, int, int)':
towns.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 1; i < leafs.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:130:28: warning: unused parameter 'sub' [-Wunused-parameter]
  130 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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