frontpage做网站教程,山东建设机械协会网站,湖南省建设厅官网站,简约型网站设计解析
第一眼#xff1a;Wow这么水的黑#xff1f;#xff1f; 然后写了一发二分套线段树的3log代码上去 T到飞起#xff0c;只有40…
无奈瞅了一眼标签#xff1a;单调队列 对啊 于是又写了一个上去 20 …
好啊 然后就摆烂了 qwq 果然黑题没有一个好东西
一个关键的思…解析
第一眼Wow这么水的黑 然后写了一发二分套线段树的3log代码上去 T到飞起只有40…
无奈瞅了一眼标签单调队列 对啊 于是又写了一个上去 20 …
好啊 然后就摆烂了 qwq 果然黑题没有一个好东西
一个关键的思想是把新加入的点当做单调队列中的元素 这样就能保证在联通块较小的时候被卡成R-L导致T飞 其实不难想思维还是需要加强
此外本题需要提前把点分治的树建出来 大大减小常数 而代码难度几乎没有提高
代码
#includebits/stdc.h
using namespace std;
#define ll long long
//#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N1e5100;
const int M2e510500;
const double eps1e-5;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,L,R,oo;
struct node{int to,nxt;double w;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y,int w){p[cnt](node){y,fi[x],1.0*w};fi[x]cnt;return;
}bool vis[N];
double dis[N],ans;
int dep[N],S,siz[N],mmx[N],rt,G[N];double mx[N];
int q[N],st,ed,tag[N],tim;
int nw[N],tot;
#define Mx(o) (tag[o]tim?mx[o]:-2e11)int num;
void find(int x,int f){siz[x]1;mmx[x]0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]||tof) continue;find(to,x);//printf( %d-%d siz:%d%d\n,x,to,siz[x],siz[to]);siz[x]siz[to];mmx[x]max(mmx[x],siz[to]);}mmx[x]max(mmx[x],S-siz[x]);if(!rt||mmx[rt]mmx[x]) rtx;//printf( x%d mx%d (rt%d) siz%d\n,x,mx[x],rt,siz[x]);return;
}
void init(int x){Ssiz[x];rt0;find(x,0);xrt;vis[rt]1;G[num]x;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;init(to);}
}int jd[N];
void bfs(int x){dep[x]1;nw[1]x;jd[x]tim;int st(1),ed(1);while(sted){int nownw[st];for(int ifi[now];~i;ip[i].nxt){int top[i].to;if(vis[to]||jd[to]tim) continue;jd[to]tim;dep[to]dep[now]1;dis[to]dis[now]p[i].w;nw[ed]to;}}toted;
}
int debug0;
void solve(int x){//xG[num];Ssiz[x];rt0;find(x,0);xrt;vis[x]1;tim;if(debug)printf(\n-----solve:rt%d\n,x);mx[0]0;tag[0]tim;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;dis[to]p[i].w;bfs(to);st1,ed0;int pl(0);if(debug) printf(to%d\n,to);for(int dmin(R,dep[nw[tot]]);d0;d--){int liL-d,riR-d;while(pltotdep[nw[pl1]]ri){pl;while(steddis[q[ed]]dis[nw[pl]]) ed--;q[ed]nw[pl];}while(steddep[q[st]]li) st;if(sted) ansmax(ans,dis[q[st]]Mx(d));if(debug) printf( d%d x%d %.2lf %.2lf\n,d,q[st],dis[q[st]],Mx(d));if(debug) if(ans0){printf(!\n);exit(0);}}for(int o1;otot;o){int nownw[o];if(Mx(dep[now])dis[now]){mx[dep[now]]dis[now];tag[dep[now]]tim;}}}for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;solve(to);}return;
}bool check(double v){for(int i0;icnt;i) p[i].w-v;num0;memset(vis,0,sizeof(vis));ans-2e11;siz[1]n;solve(1);for(int i0;icnt;i) p[i].wv;//printf(ans%lf\n,ans);return ans0;
}int main(){
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();Lread();Rread();//assert(n5000);int mn(1000000),mx(0);for(int i1;in;i){int xread(),yread(),wread();mnmin(mn,w);mxmax(mx,w);addline(x,y,w);addline(y,x,w);}//siz[1]n;init(1);if(debug){printf(%d\n,check(6.4));return 0;}double stmn,edmx;while(ed-steps){double mmid(sted)/2;if(check(mmid)) stmmid;else edmmid;}//printf(%d\n,oo);printf(%.3lf,st);return 0;
}
/*
*/
