Submission #859668

#	Time	Username	Problem	Language	Result	Execution time	Memory
859668		lbadea1000	Race (IOI11_race)	C++17	0 / 100	2 ms	9560 KiB

race

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

const int NMAX = 1e5;
const int INF = 1e9;

int totalSize;
vector<pair<int, int>> edges[NMAX];
vector<pair<long long, int>> distCentroidSubtree[NMAX];
int sz[NMAX];
int centroidParent[NMAX];
bool isIn[NMAX];

int dfsCalcSize(int node, int parent) {
    sz[node] = 1;
    for(auto child : edges[node]) {
        if(child.first != parent && isIn[child.first]) {
            sz[node] += dfsCalcSize(child.first, node);
        }
    }
    return sz[node];
}

int dfsDetCentroid(int node, int parent) {
    for(auto child : edges[node]) {
        if(child.first != parent && sz[child.first] > totalSize / 2 && isIn[child.first]) {
            return dfsDetCentroid(child.first, node);
        }
    }
    return node;
}

void computeDist(int centroid, int node, int parent, int depth, long long sum) {
    distCentroidSubtree[centroid].push_back({sum, depth});
    for(auto child : edges[node]) {
        if(isIn[child.first] && child.first != parent) {
            computeDist(centroid, child.first, node, depth + 1, sum + child.second);
        }
    }
}

void decompose(int root, int parent) {
    totalSize = dfsCalcSize(root, root);
    int centroid = dfsDetCentroid(root, root);
    computeDist(centroid, centroid, centroid, 0, 0);
    isIn[centroid] = false;
    centroidParent[centroid] = parent;
    for(auto child : edges[centroid]) {
        if(isIn[child.first])
            decompose(child.first, centroid);
    }
}

bool cmp(pair<long long, int> a, pair<long long, int> b) {
    return a.first < b.first || (a.first == b.first && a.second < b.second);
}

int best_path(int n, int k, int h[][2], int len[]) {
    for(int i = 0; i < n - 1; i++) {
        edges[h[i][0]].push_back({h[i][1], len[i]});
        edges[h[i][1]].push_back({h[i][0], len[i]});
    }
    for(int i = 0; i < n; i++)
        isIn[i] = true;
    decompose(0, -1);
    int answer = INF;
    for(int i = 0; i < n; i++) {
        sort(distCentroidSubtree[i].begin(), distCentroidSubtree[i].end(), cmp);
        /*cout << i << " : " << endl;
        for(int st = 0; st < distCentroidSubtree[i].size(); st++)
            cout << distCentroidSubtree[i][st].first << ' ';
        cout << endl;*/
        int dr = distCentroidSubtree[i].size() - 1;
        for(int st = 0; st < distCentroidSubtree[i].size(); st++) {
            while(dr > st && distCentroidSubtree[i][st].first + distCentroidSubtree[i][dr].first > k)
                dr--;
            if(distCentroidSubtree[i][st].first + distCentroidSubtree[i][dr].first == k)
                answer = min(answer, distCentroidSubtree[i][st].second + distCentroidSubtree[i][dr].second);
        }
    }
    if(answer == INF)
        answer = -1;
    return answer;
}

/*int h[NMAX][2];
int len[NMAX];

int main() {
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n - 1; i++)
        cin >> h[i][0] >> h[i][1];
    for(int i = 0; i < n - 1; i++)
        cin >> len[i];
    cout << best_path(n, k, h, len);
    return 0;
}*/

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:75:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int st = 0; st < distCentroidSubtree[i].size(); st++) {
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57