Submission #126250

#	Time	Username	Problem	Language	Result	Execution time	Memory
126250		ksmzzang2003	Race (IOI11_race)	C++14	0 / 100	12 ms	9088 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;
int N,K,L[200003];
int par[200003],sz[200003];
vector <pii> adj[200003];
int check[1000003];
bool del[200003];
int ans = 1987654321;
vector <pii> lazy;
vector <int> usecheck;
int dfs1(int now,int prev)
{
    sz[now]  =0;
    bool reaf=true;
    for(int i=0;i<adj[now].size();i++)
    {
        int next = adj[now][i].first;
        int cost = adj[now][i].second;
        if(next == prev) continue;
        if(del[next]) continue;
        reaf = false;
        sz[now] += dfs1(next,now);
    }
    return ++sz[now];
}
 
int find_cen(int now,int prev)
{
    for(int i=0;i<adj[now].size();i++)
    {
        int next = adj[now][i].first;
        int cost = adj[now][i].second;
        if(next == prev) continue;
        if(del[next]) continue;
        if(sz[next]*2>sz[now]) return find_cen(next,now);
    }
    return now;
}
 
int dfs2(int now,int prev,int sum,int depth)
{
    int ret = 1987654321;
    if(sum>K) return 1987654321;
    if(check[K-sum]!=-1)
        ret= min(ret,depth + check[K-sum]);
    lazy.push_back(pii(sum,depth));
    for(int i=0;i<adj[now].size();i++)
    {
        int next = adj[now][i].first;
        int cost = adj[now][i].second;
        if(next == prev) continue;
        if(del[next]) continue;
        ret = min(ret,dfs2(next,now,sum+cost,depth+1));
        if(sum==0)
        {
            for(pii &it:lazy) check[it.first] = it.second,usecheck.push_back(it.first);
            lazy.clear();
        }
    }
    return ret;
}
 
void g(int now,int prev)
{
    dfs1(now,-1);
    int cen = find_cen(now,-1);
    for(int &it:usecheck) check[it] = -1; usecheck.clear();
    check[0] = 0;
    ans = min(ans,dfs2(cen,-1,0,0));
    del[cen] = true;
    for(int i=0;i<adj[cen].size();i++)
    {
        int next = adj[cen][i].first;
        int cost = adj[cen][i].second;
        if(next == prev) continue;
        if(del[next]) continue;
        g(next,now);
    }
}
 
int best_path(int n, int k, int h[][2], int l[])
{
    memset(check,-1,sizeof(check));
    N= n ; K = k;
    for(int i=0;i<n-1;i++)
    {
        adj[h[i][0]].push_back(pii(h[i][1],l[i]));
        adj[h[i][1]].push_back(pii(h[i][0],l[i]));
    }
    g(1,-1);
    return (ans>=1987654300)?-1:ans;
}

Compilation message (stderr)

race.cpp: In function 'int dfs1(int, int)':
race.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[now].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:20:13: warning: unused variable 'cost' [-Wunused-variable]
         int cost = adj[now][i].second;
             ^~~~
race.cpp:16:10: warning: variable 'reaf' set but not used [-Wunused-but-set-variable]
     bool reaf=true;
          ^~~~
race.cpp: In function 'int find_cen(int, int)':
race.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[now].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:34:13: warning: unused variable 'cost' [-Wunused-variable]
         int cost = adj[now][i].second;
             ^~~~
race.cpp: In function 'int dfs2(int, int, int, int)':
race.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[now].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp: In function 'void g(int, int)':
race.cpp:69:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int &it:usecheck) check[it] = -1; usecheck.clear();
     ^~~
race.cpp:69:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int &it:usecheck) check[it] = -1; usecheck.clear();
                                           ^~~~~~~~
race.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[cen].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:76:13: warning: unused variable 'cost' [-Wunused-variable]
         int cost = adj[cen][i].second;
             ^~~~

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