为了AC 运输计划 vijos的强大数据
写了个手写栈
然后
慢一点点啊 那手写手写栈里的栈？【真TM绕口
多对了一个点诶
于是开始各种优化 inline register 什么乱七八糟的 然而一点变化都没有
我：TM这么个常数我砍不掉？
然后看隔壁CJL的最慢点只要200+ms。。（虽然WA了
我：我写的有这么丑？
然后开始检查反思。。
突然我想到了什么
然后把vector改成了邻接表
TMD丧心病狂啊
贴个代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
// <transport.cpp> - 02/07/16 12:23:52 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #include <ctime> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=300002; int i,j,k; int n,m,tot=-1,maxl; int f[MAXN],size[MAXN],son[MAXN],top[MAXN],dep[MAXN],dis[MAXN],fb[MAXN],len[MAXN]; int s[MAXN],dfn[MAXN]; int b[MAXN],to[MAXN<<1],val[MAXN<<1],sec[MAXN<<1]; struct PLAN{ int a,b,v; bool operator <(PLAN b) const{return v<b.v;} }plan[MAXN]; inline void dfs(){ s[k=1]=1; while(k){ int now=s[k--]; dfn[++j]=now; size[now]=1; for(i=b[now];i;i=sec[i]){ int next=to[i]; if(next==f[now])continue; f[next]=now; dep[next]=dep[now]+1; dis[next]=dis[now]+val[i]; s[++k]=next; } } for(i=n;i>=1;i--){ int now=dfn[i]; size[f[now]]+=size[now]; if(size[now]>size[son[f[now]]])son[f[now]]=now; } } inline void dfs2(){ top[1]=1; s[k=1]=1; while(k){ int now=s[k--]; fb[now]=++tot; len[tot]=dis[now]-dis[f[now]]; for(i=b[now];i;i=sec[i]){ int next=to[i]; if(next!=f[now]&&next!=son[now]){top[next]=next;s[++k]=next;} } if(son[now]){top[son[now]]=top[now];s[++k]=son[now];} } } inline int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); x=f[top[x]]; } if(dep[x]<dep[y])swap(x,y); return y; } int q[MAXN],cs[MAXN]; inline void cf(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); cs[fb[top[x]]]++; cs[fb[x]+1]--; x=f[top[x]]; } if(dep[x]<dep[y])swap(x,y); cs[fb[y]+1]++; cs[fb[x]+1]--; } inline bool check(int x){ for(i=1;i<=m&&plan[i].v<=x;i++); int l=m-i+1; if(!q[l]){ for(j=1;j<=n;j++)cs[j]=0; for(;i<=m;i++)cf(plan[i].a,plan[i].b); int now=0; for(j=1;j<=n;j++){ now+=cs[j]; if(now==l)q[l]=max(q[l],len[j]); } } return maxl-q[l]<=x; } int main(){ freopen("substring.in","r",stdin); freopen("substring.out","w",stdout); n=getint(),m=getint(); for(i=1;i<=n-1;i++){ int u=getint(),v=getint(),w=getint(); val[i]=w; to[i]=v; val[i+n]=w;to[i+n]=u; sec[i]=b[u];b[u]=i; sec[i+n]=b[v];b[v]=i+n; } dfs();dfs2(); for(i=1;i<=m;i++){ int u=getint(),v=getint(); plan[i].a=u; plan[i].b=v; plan[i].v=dis[u]+dis[v]-(dis[lca(u,v)]<<1); maxl=max(maxl,plan[i].v); } sort(plan+1,plan+m+1); int l=0,r=maxl; while(l<r){ int m=(l+r)>>1; if(check(m))r=m; else l=m+1; } printf("%d",l); return 0; } |
于是又去试了一下疫情控制
原来：
（WA是long long问题）
改成邻接表
你不错
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
// <blockade.cpp> - 02/11/16 08:47:22 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int INF=1000000000; const int MAXN=50003; int a[MAXN],f[MAXN][20]; lol d[MAXN][20],val[MAXN<<1]; int b[MAXN],to[MAXN<<1],sec[MAXN<<1]; int n,m; void dfs(int x){ for(int i=b[x];i;i=sec[i]){ int next=to[i]; if(next==f[x][0])continue; f[next][0]=x; d[next][0]=val[i]; dfs(next); } } struct am{int x;lol d;}; bool cmp(am a,am b){return a.d<b.d;} bool vis[MAXN]; vector <am> yy,zz; void dfs2(int x){ if(vis[x])return;bool nl=0,yes=1; for(int i=b[x];i;i=sec[i]){ int next=to[i]; if(next==f[x][0])continue; nl=1; dfs2(next); if(!vis[next])yes=0; } vis[x]=nl&yes; } bool check(lol x){ yy.clear();zz.clear(); for(int i=1;i<=n;i++)vis[i]=0; for(int i=1;i<=m;i++){ int now=a[i];lol dist=x; for(int j=19;j>=0;j--) if(f[now][j]!=1&&f[now][j]!=0&&d[now][j]<=dist){ dist-=d[now][j]; now=f[now][j]; } if(f[now][0]==1&&dist>d[now][0])yy.push_back((am){now,dist-d[now][0]}); else vis[now]=1; } sort(yy.begin(),yy.end(),cmp); dfs2(1); for(int i=b[1];i;i=sec[i]) if(!vis[to[i]]) zz.push_back((am){to[i],val[i]}); if(!zz.size())return 1; sort(zz.begin(),zz.end(),cmp); int now=0; for(int i=0;i<yy.size();i++){ if(vis[zz[now].x]){i--;if(++now==zz.size())return 1;} else if(!vis[yy[i].x])vis[yy[i].x]=1; else if(yy[i].d>=zz[now].d){vis[zz[now].x]=1;if(++now==zz.size())return 1;} } while(vis[zz[now].x])if(++now==zz.size())return 1; return 0; } int main(){ freopen("blockade.in","r",stdin); freopen("blockade.out","w",stdout); n=getint(); lol l=0,r,rr=0; for(int i=1;i<n;i++){ int u=getint(),v=getint(),w=getint(); val[i]=w; to[i]=v; val[i+n]=w;to[i+n]=u; sec[i]=b[u];b[u]=i; sec[i+n]=b[v];b[v]=i+n; rr+=w; } m=getint(); for(int i=1;i<=m;i++)a[i]=getint(); dfs(1); for(int j=1;j<20;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1],d[i][j]=d[i][j-1]+d[f[i][j-1]][j-1]; r=rr+1; while(l<r){ int mid=(l+r)>>1; if(check(mid))r=mid; else l=mid+1; } if(l==rr+1)cout<<-1; else cout<<l; return 0; } |
以后都不敢用STL容器了