Testing Blog

Revision en15, by suncongbo, 2018-06-23 11:45:23

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 Codeforces Round 250 (Div. 1) 530A - Quadratic equation

#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; void addedge(int u,int v,int w) { 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; addedge(x,y,z); addedge(y,x,z); } 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; }

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en25 English suncongbo 2018-06-23 11:58:47 147
en24 English suncongbo 2018-06-23 11:54:06 0 (published)
en23 English suncongbo 2018-06-23 11:53:28 10
en22 English suncongbo 2018-06-23 11:52:50 57
en21 English suncongbo 2018-06-23 11:51:43 58
en20 English suncongbo 2018-06-23 11:51:01 4
en19 English suncongbo 2018-06-23 11:50:36 44
en18 English suncongbo 2018-06-23 11:49:52 143
en17 English suncongbo 2018-06-23 11:46:28 2026
en16 English suncongbo 2018-06-23 11:46:11 2061
en15 English suncongbo 2018-06-23 11:45:23 2029
en14 English suncongbo 2018-06-23 11:44:43 2041
en13 English suncongbo 2018-06-23 11:43:36 2088
en12 English suncongbo 2018-06-23 11:42:36 4
en11 English suncongbo 2018-06-23 11:41:09 19
en10 English suncongbo 2018-06-23 11:40:46 57
en9 English suncongbo 2018-06-23 11:38:35 6
en8 English suncongbo 2018-06-23 11:38:20 6
en7 English suncongbo 2018-06-23 11:38:02 6
en6 English suncongbo 2018-06-23 11:37:47 6
en5 English suncongbo 2018-06-23 11:37:24 11
en4 English suncongbo 2018-06-23 11:36:51 95
en3 English suncongbo 2018-06-23 11:36:18 40
en2 English suncongbo 2018-06-23 11:34:23 133
en1 English suncongbo 2018-06-23 11:32:19 222 Initial revision (saved to drafts)