分糖果+对抗赛

对抗赛

这个题实力演绎了什么叫做玄学。。。加快读就过不加快读就不过=_=本地编译的时候跑出来明明是对的放到测评机来跑就能跑出来个零

分糖果

数据已经毒到一定境界了，第一次 60

#include<bits/stdc++.h>
using namespace std;
int n,m,p,c,cnt,ans;
int head[100010],vis[100010],dis[100010];
struct node{int to,next,val;}e[2000010];
void add_edge(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=1;head[u]=cnt;
}
int main()
{freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);memset(dis,0x3f3f3f,sizeof dis);memset(head,0,sizeof head);scanf("%d%d%d%d",&n,&p,&c,&m);for(int i=1;i<=p;i++){int u,v,w;scanf("%d%d",&u,&v);add_edge(u,v);add_edge(v,u);}dis[c]=0;vis[c]=1;queue<int>q;q.push(c);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(dis[u]+e[i].val<dis[v]){dis[v]=dis[u]+e[i].val;ans=max(ans,dis[v]);if(!vis[v]){q.push(v);vis[v]=1;}}}vis[u]=0;}printf("%d",ans+m+1);return 0;
}
/*
4 3 1
2
1 2
2 3
1 4
*/

第二次70

#include<bits/stdc++.h>
using namespace std;
int n,m,p,c,cnt,a,b=1,q[100010][2],head[100010];
struct node{int to,next;}e[2000010];
bool vis[100010];
void add_edge(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
void bfs()
{q[1][0]=c,q[1][1]=1;vis[c]=1;while(b>a){a++;for(int i=head[q[a][0]];i;i=e[i].next){if(!vis[e[i].to]){q[++b][0]=e[i].to;q[b][1]=q[a][1]+1;vis[e[i].to]=1;}}}
}
int main()
{freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);memset(head,0,sizeof head);scanf("%d%d%d%d",&n,&p,&c,&m);for(int i=1;i<=p;i++){int u,v;scanf("%d%d",&u,&v);add_edge(u,v);add_edge(v,u);}bfs();printf("%d",q[b][1]+m); return 0;
}
/*
4 3 1
2
1 2
2 3
1 4
*/

最后用上了平生所学所有优化技巧。所以日常优化很重要

#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,m,f,t,head[N],dis[N],cnt;
struct edge
{ int to,nxt; } e[2000010];
int read()
{int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;
}
inline void add(int u,int v)
{e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
typedef pair<int,int> pr;
priority_queue<pr,vector<pr>,greater<pr> > q;
inline void dij()
{memset(dis,0x3f3f3f3f,sizeof(dis));dis[f]=1;q.push(make_pair(1,f));while(!q.empty()){int x=q.top().second;q.pop();for(register int i(head[x]); i; i=e[i].nxt){int v=e[i].to;if(dis[v]>dis[x]+1)dis[v]=dis[x]+1,q.push(make_pair(dis[v],v));}}
}
int main()
{freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);n=read(),m=read(),f=read(),t=read();for(register int i=1; i<=m; ++i){int u=read();int v=read();add(u,v);add(v,u);}dij();int ans=0;for(register int i=1; i<=n; ++i) ans=max(ans,dis[i]);printf("%d",ans+t);return 0;
}

所以：

1. 快读
2. register int
3. ++i
4. inline void/int
5. 习惯性priority

随手优化