Submission #547940

#	Time	Username	Problem	Language	Result	Execution time	Memory
547940		ZuZKho	경주 (Race) (IOI11_race)	C++17	43 / 100	3065 ms	34208 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);
int Ans = 1e9;
int n,k;

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;
}
vector<pair<int,int> > cur;
void dfs_func(int v,int p,pair<int,int> func) {
    if (func.first>k) return;
    cur.push_back(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});
    }
}

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

void solve(int v) {

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

    ans[0] = 0;
    changed.push_back(0);
    for(int i=0;i<g[c].size();i++) {
        int ch = g[c][i].first;
        cur.clear();
        dfs_func(ch,c,{g[c][i].second,1});

        for(int j=0;j<cur.size();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<cur.size();j++) {
            int len = cur[j].first, cnt = cur[j].second;
            if (ans[len] == -1) {
                ans[len] = cnt;
                changed.push_back(len);
            }
            else ans[len] = min(ans[len],cnt);
        }
    }
    for(int i=0;i<changed.size();i++) {
        ans[changed[i]] = -1;
    }
    changed.clear();
    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:15: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]
   15 |     for(int i=0;i<g[v].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:24: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]
   24 |     for(int i=0;i<g[v].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void dfs_func(int, int, std::pair<int, int>)':
race.cpp:36: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]
   36 |     for(int i=0;i<g[v].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:56: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]
   56 |     for(int i=0;i<g[c].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp:61:22: 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 j=0;j<cur.size();j++) {
      |                     ~^~~~~~~~~~~
race.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int j=0;j<cur.size();j++) {
      |                     ~^~~~~~~~~~~
race.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<changed.size();i++) {
      |                 ~^~~~~~~~~~~~~~~
race.cpp:78: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]
   78 |     for(int i=0;i<g[c].size();i++) {
      |                 ~^~~~~~~~~~~~

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