suncongbo's blog

By suncongbo, history, 5 months ago, ,

This is suncongbo's blog. This entry is just for testing.

Markdown Test

Markdown Test

MD Test:

MD Test:

Created, edited and deleted successfully.

Inline Code:  int main() { printf("Hello World!\n"); //Hello world }

Reference:

suncongbo refers to me at 20171013

suncongbo refers to me at 20180530

Codeforces Round #439 (Div. 2)

438A - The Child and Toy refers to a contest by vfleaking

Block Code: Empty lines are now allowed in the code. An empty line is requested above the code.

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e5;
const int C = 1e6;
const int INF = 1e8;
struct Edge {int nxt,v,w;} e[(N<<1)+2];
int tmp[N+2];
int t[C+2];
int dis[N+2];
int dep[N+2];
int fe[N+2];
int sz[N+2];
int cur[N+2];
bool vis[N+2];
int n,m,mn,c,rt,siz,ans,tp;
{
m++; e[m].v = v; e[m].w = w;
e[m].nxt = fe[u]; fe[u] = m;
}
void getroot(int u,int prv)
{
sz[u] = 1; cur[u] = 0;
for(int i=fe[u]; i; i=e[i].nxt)
{
if(e[i].v==prv || vis[e[i].v]==true) continue;
getroot(e[i].v,u);
sz[u] += sz[e[i].v]; cur[u] = max(cur[u],sz[e[i].v]);
}
cur[u] = max(cur[u],siz-sz[u]);
if(cur[u]<mn) {mn = cur[u]; rt = u;}
}
void dfs(int u,int prv)
{
tp++; tmp[tp] = u;
for(int i=fe[u]; i; i=e[i].nxt)
{
if(vis[e[i].v]==true || e[i].v==prv) continue;
dep[e[i].v] = dep[u]+1; dis[e[i].v] = dis[u]+e[i].w;
if(dis[e[i].v]>c) dis[e[i].v] = c+1;
dfs(e[i].v,u);
}
}
void pdc(int u)
{
vis[u] = true;
tp = 0;
for(int i=fe[u]; i; i=e[i].nxt)
{
if(vis[e[i].v]==true) continue;
dis[e[i].v] = e[i].w; dep[e[i].v] = 1;
dfs(e[i].v,u);
for(int j=1; j<=tp; j++) {if(dis[tmp[j]]<c) ans = min(ans,t[c-dis[tmp[j]]]+dep[tmp[j]]);}
for(int j=1; j<=tp; j++) {if(dis[tmp[j]]<=c) t[dis[tmp[j]]] = min(t[dis[tmp[j]]],dep[tmp[j]]);}
ans = min(ans,t[c]);
}
for(int i=1; i<=tp; i++) {if(dis[tmp[i]]<=c) t[dis[tmp[i]]] = INF;}
for(int i=fe[u]; i; i=e[i].nxt)
{
if(vis[e[i].v]==true) continue;
rt = 0; mn = INF; siz = sz[e[i].v];
getroot(e[i].v,0); pdc(rt);
}
}
int main()
{
scanf("%d%d",&n,&c); m = 0;
if(c==0) {puts("0"); return 0;}
for(int i=1; i<n; i++)
{
int x,y,z; scanf("%d%d%d",&x,&y,&z); x++; y++;
if(z>c) z = c+1;
}
for(int i=1; i<=c; i++) t[i] = INF;
siz = sz[1] = n; rt = 0; ans = INF; mn = INF;
getroot(1,0); pdc(rt);
printf("%d\n",ans==INF ? -1 : ans);
return 0;
}


Saved as a draft: "You are not allowed to view the requested page"

Deleted: "No such topic"

Have not yet been published: "No such blog entry"

•
• +5
•

 » 5 months ago, # |   +1 Auto comment: topic has been updated by suncongbo (previous revision, new revision, compare).
 » 5 months ago, # |   +1 Auto comment: topic has been updated by suncongbo (previous revision, new revision, compare).
 » 5 months ago, # |   -14 you are so strong！！
•  » » 5 months ago, # ^ |   +6 You Are So Strong！