| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 71623 |
2018-08-25T08:57:02 Z |
MANcity |
Race (IOI11_race) |
C++14 |
|
7 ms |
5112 KB |
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "race.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int K;
vector<vector<pair<int,int> > > G(200002);
int sizeVer[200002];
int used[200002];
int sumSize;
int verNum;
int ka[1000002];
int ANSWER=1000000;
void dfs(int v,int p)
{
if(G[v].size()==1 && G[v][0].first==p)
sizeVer[v]=1;
else
sizeVer[v]=0;
for0(j,G[v].size()-1)
{
int to=G[v][j].first;
if(to!=p && used[to]==0)
{
dfs(to,v);
sizeVer[v]+=sizeVer[to];
}
}
verNum++;
sizeVer[v]+=1;
sumSize+=sizeVer[v];
}
int find_centr(int v,int p)
{
int u=0;
for0(j,G[v].size()-1)
{
int to=G[v][j].first;
if(to!=p && used[to]==0)
{
if(2*sizeVer[to]>verNum)
{
u=1;
return find_centr(to,v);
}
}
}
if(u==0)
return v;
}
int update_dfs(int v,int p,int len,int qan)
{
if(ka[len]==-1)
ka[len]=qan;
else
ka[len]=min(qan,ka[len]);
for0(j,G[v].size()-1)
{
int to=G[v][j].first;
int l=G[v][j].second;
if(to!=p && used[to]==0)
{
update_dfs(to,v,len+l,qan+1);
}
}
}
int stug_dfs(int v,int p,int len,int qan)
{
if(K>=len)
{
if(ka[K-len]!=-1)
ANSWER=min(ANSWER,ka[K-len]+qan);
}
if(K<=len)
for0(j,G[v].size()-1)
{
int to=G[v][j].first;
int l=G[v][j].second;
if(to!=p && used[to]==0)
{
stug_dfs(to,v,len+l,qan+1);
}
}
}
void solve(int v)
{
for0(i,K)
ka[i]=-1;
ka[0]=0;
sumSize=0;
verNum=0;
dfs(v,-1);
if(verNum==1)
return;
int centr=find_centr(v,-1);
for0(i,G[centr].size()-1)
{
int to=G[centr][i].first;
int len=G[centr][i].second;
if(used[to]==0)
{
update_dfs(to,v,len,1);
stug_dfs(to,v,len,1);
}
}
used[centr]=1;
for0(i,G[centr].size()-1)
{
int to=G[centr][i].first;
if(used[to]==0)
{
solve(to);
}
}
}
int best_path(int N, int K_0, int H[][2], int L[])
{
K=K_0;
for0(i,N-2)
{
G[H[i][0]].pb({H[i][1],L[i]});
G[H[i][1]].pb({H[i][0],L[i]});
}
solve(1);
if(ANSWER=1000000)
return -1;
return ANSWER;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/
Compilation message
race.cpp: In function 'int update_dfs(int, int, int, int)':
race.cpp:84:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'int stug_dfs(int, int, int, int)':
race.cpp:102:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:143:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if(ANSWER=1000000)
~~~~~~^~~~~~~~
race.cpp: In function 'int find_centr(int, int)':
race.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
