Submission #547956

#	Time	Username	Problem	Language	Result	Execution time	Memory
547956		ZuZKho	Race (IOI11_race)	C++17	100 / 100	423 ms	41800 KiB

race

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

using namespace std;

const int MAXN = 200005;
vector<pair<int,int> > g[MAXN];
vector<char> used(MAXN,0);
vector<int> sz(MAXN,0);
vector<pair<int,int> > cur(MAXN);
int Ans = 1e9;
int n,k;

const int MAXK = 1e6 + 10;
vector<int> ans(MAXK,-1);
vector<int> changed(MAXK);

int cursz = 0;
int chsz = 0;

void dfs_sizes(int v,int p) {
    sz[v] = 1;
    for(int i=0;i<g[v].size();i++) {
        int to = g[v][i].first;
        if (to==p || used[to]) continue;
        dfs_sizes(to,v);
        sz[v]+=sz[to];
    }
}

int centroid(int v,int p,int ss) {
    for(int i=0;i<g[v].size();i++) {
        int to = g[v][i].first;
        if (to==p || used[to]) continue;
        if (sz[to] > ss/2) return centroid(to,v,ss);
    }
    return v;
}

void dfs_func(int v,int p,pair<int,int> func) {
    if (func.first>k) return;
    cur[cursz++] = func;
    int len = func.first, cnt = func.second;
    for(int i=0;i<g[v].size();i++) {
        int to = g[v][i].first;
        if (to==p || used[to]) continue;
        if (len+g[v][i].second > k) return;
        dfs_func(to,v,{len+g[v][i].second,cnt+1});
    }
}


void solve(int v) {

    dfs_sizes(v,-1);
    int c = centroid(v,-1,sz[v]);
    used[c] = 1;

    ans[0] = 0;
    changed[chsz++] = 0;
    for(int i=0;i<g[c].size();i++) {
        int ch = g[c][i].first;
        if (used[ch]) continue;
        cursz = 0;
        dfs_func(ch,c,{g[c][i].second,1});

        for(int j=0;j<cursz;j++) {
            int len = cur[j].first, cnt = cur[j].second;
            if (ans[k-len]!=-1) Ans = min(Ans,ans[k-len] + cnt);
        }
        for(int j=0;j<cursz;j++) {
            int len = cur[j].first, cnt = cur[j].second;
            if (ans[len] == -1) {
                ans[len] = cnt;
                changed[chsz++] = len;
            }
            else ans[len] = min(ans[len],cnt);
        }
    }
    for(int i=0;i<chsz;i++) {
        ans[changed[i]] = -1;
    }
    chsz = 0;
    for(int i=0;i<g[c].size();i++) {
        if (!used[g[c][i].first]) solve(g[c][i].first);
    }
}


int best_path(int _n, int _k, int h[][2], int l[]) {

    n = _n;
    k = _k;
    for(int i=0;i<n-1;i++) {
        int u = h[i][0],v=h[i][1],len = l[i];
        g[u].push_back({v,len});
        g[v].push_back({u,len});
    }

    solve(0);

    if (Ans==1e9) return -1; else return Ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs_sizes(int, int)':
race.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<g[v].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<g[v].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void dfs_func(int, int, std::pair<int, int>)':
race.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<g[v].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<g[c].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<g[c].size();i++) {
      |                 ~^~~~~~~~~~~~

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