Submission #353981

#	Time	Username	Problem	Language	Result	Execution time	Memory
353981		xt0r3	Race (IOI11_race)	C++14	100 / 100	1089 ms	42204 KiB

race

#include<bits/stdc++.h>
#include "race.h"

using namespace std;

constexpr int MAXN = 2*1e5 + 5, MAXK = 1e6 + 5, INF = 1e8;
bool visited[MAXN];
int c[MAXN], k, mini[MAXK];
vector<int> edges[MAXN], w[MAXN];

int cnt(int id){
    visited[id] = 1;
    c[id] = 1;
    for(int v : edges[id]) if(!visited[v]) c[id] += cnt(v);
    visited[id] = 0;
    return c[id];
}

int init(int id, int n, int p = -1){
    for(int v : edges[id]) if(c[v] > n/2 && !visited[v] && p != v) return init(v, n, id);
    return id;
}

int centroid(int id){
    return init(id, cnt(id));
}

int calc(int id, int len, int lvl = 1, int p = -1){
    int ret = INF;
    if(len <= k) ret = min(ret, mini[k-len] + lvl);
    for(int i = 0; i < edges[id].size(); i++){
        int v = edges[id][i];
        if(!visited[v] && v != p) ret = min(ret, calc(v, min(INF, len + w[id][i]), lvl + 1, id));
    }
    return ret;
}

void add(int id, int len, int lvl = 1, int p = -1){
    if(len < MAXK) mini[len] = min(mini[len], lvl);
    for(int i = 0; i < edges[id].size(); i++){
        int v = edges[id][i];
        if(!visited[v] && p != v) add(v, min(INF, len + w[id][i]), lvl + 1, id);
    }
}

void res(int id, int len = 0, int p = -1){
    if(len < MAXK) mini[len] = INF;
    for(int i = 0; i < edges[id].size(); i++){
        int v = edges[id][i];
        if(!visited[v] && p != v) res(v, min(INF, len + w[id][i]), id);
    }
}

int db(int id){
    int ret = INF;
    mini[0] = 0;
    for(int i = 0; i < edges[id].size(); i++){
        int v = edges[id][i];
        //cout << v << ' ' << visited[v] << endl;
        if(visited[v]) continue;
        ret = min(ret, calc(v, w[id][i], 1, id));
        //cout << "ITT" << endl;
        add(v, w[id][i], 1, id);
        //cout << "ITT" << endl;
    }
    res(id);
    return ret;
}

int process(int id){
    //cout << "eppen: " << id << endl;
    int ret = db(id);
    visited[id] = 1;
    for(int v : edges[id]) if(!visited[v]) ret = min(ret, process(centroid(v)));
    //cout << id << ' ' << ret << endl;
    return ret;
}



int best_path(int N, int K, int H[][2], int L[])
{
    fill(mini, mini + MAXK, INF);
    k = K;
    for(int i = 0; i < N-1; i++){
        edges[H[i][0]].push_back(H[i][1]);
        w[H[i][0]].push_back(L[i]);
        swap(H[i][0], H[i][1]);
        edges[H[i][0]].push_back(H[i][1]);
        w[H[i][0]].push_back(L[i]);
    }
    int ret = process(centroid(0));
    return (ret == INF ? -1 : ret);
}

Compilation message (stderr)

race.cpp: In function 'int calc(int, int, int, int)':
race.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0; i < edges[id].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'void add(int, int, int, int)':
race.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < edges[id].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'void res(int, int, int)':
race.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < edges[id].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'int db(int)':
race.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0; i < edges[id].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~

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