Submission #547936

#	Time	Username	Problem	Language	Result	Execution time	Memory
547936		ZuZKho	경주 (Race) (IOI11_race)	C++17	43 / 100	3061 ms	33228 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) {
    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});
    }
}

void solve(int v) {

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

    map<int,int> mp;
    mp[0] = 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 (mp.find(k-len)!=mp.end()) Ans = min(Ans,mp[k-len] + cnt);
        }
        for(int j=0;j<cur.size();j++) {
            int len = cur[j].first, cnt = cur[j].second;
            if (mp.find(len)==mp.end()) mp[len] = cnt; else mp[len] = min(mp[len],cnt);
        }
    }
    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:35: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]
   35 |     for(int i=0;i<g[v].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:51: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]
   51 |     for(int i=0;i<g[c].size();i++) {
      |                 ~^~~~~~~~~~~~
race.cpp:55: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]
   55 |         for(int j=0;j<cur.size();j++) {
      |                     ~^~~~~~~~~~~
race.cpp:59: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]
   59 |         for(int j=0;j<cur.size();j++) {
      |                     ~^~~~~~~~~~~
race.cpp:64: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]
   64 |     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