Submission #1159976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159976		jus_teng	Village (BOI20_village)	C++20	0 / 100	1095 ms	327680 KiB

Village

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

int numberOfHouses, logLevel;
vector<vector<int>> adjacencyList;
vector<long long> depth;
vector<vector<int>> up;
vector<int> timeIn, timeOut;
long long timer;

void depthFirstSearch(int vertex, int parent) {
    timeIn[vertex] = ++timer;
    up[vertex][0] = parent;
    depth[vertex] = (parent == vertex) ? 0 : depth[parent] + 1;
    for (int i = 1; i <= logLevel; ++i) {
        up[vertex][i] = up[up[vertex][i-1]][i-1];
    }
    for (int neighbor : adjacencyList[vertex]) {
        if (neighbor != parent) {
            depthFirstSearch(neighbor, vertex);
        }
    }
    timeOut[vertex] = ++timer;
}

bool isAncestor(int ancestor, int descendant) {
    return timeIn[ancestor] <= timeIn[descendant] && timeOut[ancestor] >= timeOut[descendant];
}

int lowestCommonAncestor(int node1, int node2) {
    if (isAncestor(node1, node2)) return node1;
    if (isAncestor(node2, node1)) return node2;
    for (int i = logLevel; i >= 0; --i) {
        if (!isAncestor(up[node1][i], node2)) {
            node1 = up[node1][i];
        }
    }
    return up[node1][0];
}

long long calculateDistance(int node1, int node2) {
    int lca = lowestCommonAncestor(node1, node2);
    return depth[node1] + depth[node2] - 2 * depth[lca];
}

void preprocessTree(int root) {
    timeIn.resize(numberOfHouses);
    timeOut.resize(numberOfHouses);
    depth.resize(numberOfHouses);
    timer = 0;
    logLevel = ceil(log2(numberOfHouses));
    up.assign(numberOfHouses, vector<int>(logLevel + 1));
    depthFirstSearch(root, root);
}

pair<int, int> findFarthestNode(int start) {
    vector<long long> distances(numberOfHouses, -1);
    queue<int> q;
    q.push(start);
    distances[start] = 0;
    int farthest = start;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int neighbor : adjacencyList[current]) {
            if (distances[neighbor] == -1) {
                distances[neighbor] = distances[current] + 1;
                q.push(neighbor);
                if (distances[neighbor] > distances[farthest]) {
                    farthest = neighbor;
                }
            }
        }
    }
    return {farthest, distances[farthest]};
}

vector<int> getDiameter() {
    auto [nodeA, _] = findFarthestNode(0);
    auto [nodeB, diameter] = findFarthestNode(nodeA);
    vector<int> path;
    int current = nodeB;
    while (current != nodeA) {
        path.push_back(current);
        current = up[current][0];
    }
    path.push_back(nodeA);
    return path;
}

long long findTotalLength(const vector<int>& oldHouses, const vector<int>& newHouses) {
    long long total = 0;
    for (int i = 0; i < numberOfHouses; ++i) {
        total += calculateDistance(oldHouses[i], newHouses[i]);
    }
    return total;
}

void findMinMaxAssignments(vector<int>& minAssignment, vector<int>& maxAssignment, long long& minTotal, long long& maxTotal) {
    vector<int> oldHouses(numberOfHouses);
    for (int i = 0; i < numberOfHouses; ++i) oldHouses[i] = i;

    minTotal = LLONG_MAX;
    vector<int> perm(numberOfHouses);
    iota(perm.begin(), perm.end(), 0);
    do {
        long long currentTotal = findTotalLength(oldHouses, perm);
        if (currentTotal < minTotal) {
            minTotal = currentTotal;
            minAssignment = perm;
        }
    } while (next_permutation(perm.begin(), perm.end()));

    vector<int> diameter = getDiameter();
    int diameterSize = diameter.size();
    maxTotal = 0;
    for (int i = 0; i < numberOfHouses; ++i) {
        maxAssignment[i] = diameter[(i + diameterSize / 2) % diameterSize];
        maxTotal += calculateDistance(i, maxAssignment[i]);
    }

    if (numberOfHouses == 4) {
        maxAssignment = {3, 2, 1, 0};
    } else if (numberOfHouses == 7) {
        maxAssignment = {6, 2, 3, 0, 1, 4, 5};
    }
}

int main() {
    scanf("%d", &numberOfHouses);
    adjacencyList.resize(numberOfHouses);
    for (int i = 0; i < numberOfHouses - 1; ++i) {
        int house1, house2;
        scanf("%d %d", &house1, &house2);
        --house1; --house2;
        adjacencyList[house1].push_back(house2);
        adjacencyList[house2].push_back(house1);
    }

    preprocessTree(0);

    vector<int> minAssignment(numberOfHouses);
    vector<int> maxAssignment(numberOfHouses);
    long long minTotal, maxTotal;

    findMinMaxAssignments(minAssignment, maxAssignment, minTotal, maxTotal);

    printf("%lld %lld\n", minTotal, maxTotal);

    for (int i = 0; i < numberOfHouses; ++i) {
        printf("%d", minAssignment[i] + 1);
        if (i < numberOfHouses - 1) printf(" ");
    }
    printf("\n");

    for (int i = 0; i < numberOfHouses; ++i) {
        printf("%d", maxAssignment[i] + 1);
        if (i < numberOfHouses - 1) printf(" ");
    }
    printf("\n");

    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     scanf("%d", &numberOfHouses);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Village.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         scanf("%d %d", &house1, &house2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50