Submission #570490

#	Time	Username	Problem	Language	Result	Execution time	Memory
570490		AlesL0	Race (IOI11_race)	C++17	43 / 100	3079 ms	52276 KiB

race

#pragma GCC optimize("03")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1e6;

int current, siz, k, timer = 0, sol = INF;
vector <pair<int, int>> updates;

void get_size(int c, vector <int> g[], bool b[], int s[]){
    s[c] = 1; b[c] = 1; siz++;
    for (int i = 0; i < g[c].size(); i++){
        if (!b[g[c][i]]){
            int h = g[c][i]; get_size(h, g, b, s);
            s[c] += s[h];
        }
    }
    b[c] = 0;
}

void dfs(int c, vector <int> g[], bool b[], int s[]){
    b[c] = 1; int m = 0;
    for (int i = 0; i < g[c].size(); i++){
        if (!b[g[c][i]]){
            int h = g[c][i]; dfs(h, g, b, s);
            m = max(m, s[h]);
        }
    }
    b[c] = 0;
    if (m <= siz)current = c;
}

void solve(int c, vector <int> g[], vector <int> w[], bool b[], pair<int, int> d[], ll l, int h){
    b[c] = 1;
    if (l <= k){
        if (d[k-l].second < timer){d[k-l].second = timer; d[k-l].first = INF;}
        sol = min(sol, d[k-l].first+h);
        if (l == k)sol = min(sol, h);
        if (d[l].second < timer){d[l].second = timer; d[l].first = INF;}
        updates.push_back({l, h});
    }
    for (int i = 0; i < g[c].size(); i++){
        if (!b[g[c][i]])solve(g[c][i], g, w, b, d, l+w[c][i], h+1);
    }
    b[c] = 0;
}

void centroid_decomposition(int c, vector <int> g[], vector <int> w[], bool b[], int s[], pair<int, int> d[]){
    siz = 0; get_size(c, g, b, s); siz /= 2; dfs(c, g, b, s);
    int r = current; b[r] = 1;
    for (int i = 0; i < g[r].size(); i++){
        int v = g[r][i];
        if (!b[v]){
            solve(v, g, w, b, d, w[r][i], 1);
            for (int j = 0; j < updates.size(); j++)d[updates[j].first].first = min(d[updates[j].first].first, updates[j].second);
            updates.clear();
        }
    }
    timer++;
    for (int i = 0; i < g[r].size(); i++){
        if (!b[g[r][i]])centroid_decomposition(g[r][i], g, w, b, s, d);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    vector <int> g[N], w[N]; k = K;
    pair<int, int> d[k+1]; for (int i = 0; i <= k; i++)d[i] = {INF, 0};
    for (int i = 0; i < N-1; i++){
        g[H[i][0]].push_back(H[i][1]); g[H[i][1]].push_back(H[i][0]);
        w[H[i][0]].push_back(L[i]); w[H[i][1]].push_back(L[i]);
    }
    bool b[N]; for (int i = 0; i < N; i++)b[i] = 0;
    int s[N];
    centroid_decomposition(0, g, w, b, s, d);
    if (sol == INF)sol = -1;
    return sol;
}

Compilation message (stderr)

race.cpp: In function 'void get_size(int, std::vector<int>*, bool*, int*)':
race.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < g[c].size(); i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, std::vector<int>*, bool*, int*)':
race.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < g[c].size(); i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void solve(int, std::vector<int>*, std::vector<int>*, bool*, std::pair<int, int>*, ll, int)':
race.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < g[c].size(); i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void centroid_decomposition(int, std::vector<int>*, std::vector<int>*, bool*, int*, std::pair<int, int>*)':
race.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < g[r].size(); i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp:59:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for (int j = 0; j < updates.size(); j++)d[updates[j].first].first = min(d[updates[j].first].first, updates[j].second);
      |                             ~~^~~~~~~~~~~~~~~~
race.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < g[r].size(); i++){
      |                     ~~^~~~~~~~~~~~~

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