| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 126247 |
2019-07-07T10:08:07 Z |
ksmzzang2003 |
Race (IOI11_race) |
C++14 |
|
10 ms |
9720 KB |
#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)
{
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)
{
memset(sz,0,sizeof(sz));
dfs1(now,-1);
int cen = find_cen(now,-1);
for(int &it:usecheck)
check[it] = -1;
usecheck.clear();
check[0] = 0;
lazy.clear();
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(2,-1);
return (ans>=1987654300)?-1:ans;
}
Compilation message
race.cpp: In function 'int dfs1(int, int)':
race.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[now].size(); i++)
~^~~~~~~~~~~~~~~~
race.cpp:19:13: warning: unused variable 'cost' [-Wunused-variable]
int cost = adj[now][i].second;
^~~~
race.cpp:15: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:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[now].size(); i++)
~^~~~~~~~~~~~~~~~
race.cpp:35: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:54:19: 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:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[cen].size(); i++)
~^~~~~~~~~~~~~~~~
race.cpp:88:13: warning: unused variable 'cost' [-Wunused-variable]
int cost = adj[cen][i].second;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
