제출 #859678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
859678		lbadea1000	경주 (Race) (IOI11_race)	C++17	0 / 100	3 ms	17752 KiB

race

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

const int NMAX = 1e5;
const int LOGMAX = 20;
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 level[NMAX];

int father[LOGMAX][NMAX];

void dfs(int node, int parent) {
    for(auto child : edges[node]) {
        if(child.first != parent) {
            father[0][child.first] = node;
            level[child.first] = level[node] + 1;
            dfs(child.first, node);
        }
    }
}

void make_fathers(int root, int n) {
    level[root] = 0;
    father[0][root] = 0;
    dfs(root, -1);
    for(int i = 1; i < LOGMAX; i++) {
        for(int j = 0; j < n; j++) {
            father[i][j] = father[i - 1][father[i - 1][j]];
        }
    }
}

int lca(int a, int b) {
    if(level[a] > level[b])
        swap(a, b);
    int diff = level[b] - level[a];
    for(int i = 0; i < LOGMAX; i++) {
        if(diff & (1 << i))
            b = father[i][b];
    }
    if(a == b)
        return a;
    for(int i = LOGMAX - 1; i >= 0; i--) {
        if(father[i][a] != father[i][b]) {
            a = father[i][a];
            b = father[i][b];
        }
    }
    return father[0][a];
}

int dist(int a, int b) {
    return level[a] + level[b] - 2 * level[lca(a, b)];
}

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, dist(centroid, node)});
    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]});
    }

    make_fathers(0, n);

    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;
}*/

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:126: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]
  126 |         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