72 条题解
-
-1
program543 LV 8 @ 2017-09-29 16:51:46
#include <stdio.h> #include <math.h> int n,m; struct node { int next; int u,v; int w; }; int root; int temp[100001]; int temp1[100001]; node edge[400001]; int tot; int first[100001]; int f[100001][31]; long long c[100001][31]; int deep[100001]; long long ans; int num; void find_father(int x,int fa) { for (int i=first[x];i!=0;i=edge[i].next) if (edge[i].v!=fa) { f[edge[i].v][0]=x; c[edge[i].v][0]=edge[i].w; deep[edge[i].v]=deep[x]+1; find_father(edge[i].v,x); } } inline void Add_Edge(int a,int b,int c) { edge[++tot].u=a;edge[tot].v=b;edge[tot].next=first[a];edge[tot].w=c;first[a]=tot; edge[++tot].u=b;edge[tot].v=a;edge[tot].next=first[b];edge[tot].w=c;first[b]=tot; } void init_LCA() { for (int i=1;i<=30;i++) for (int j=1;j<=n;j++) { f[j][i]=f[f[j][i-1]][i-1]; c[j][i]=c[j][i-1]+c[f[j][i-1]][i-1]; } } int LCA(int l1,int l2) { if (deep[l1]>deep[l2]) { int t=l1;l1=l2;l2=t; } int now=deep[l2]; int data=l2; if (deep[l2]!=deep[l1]) for (int i=int(log(deep[l2]-deep[l1])/log(2))+1;i>=0;i--) { if (now-(1<<i)>=deep[l1]) { data=f[data][i]; now=now-(1<<i); } } int temp1=l1; int temp2=data; int depth=deep[temp1]; if (depth==1) return root; else if (temp1==temp2) return temp2; else { for (int i=int(log(deep[temp1])/log(2))+1;i>=0;i--) if (f[temp1][i]!=f[temp2][i]) { temp1=f[temp1][i]; temp2=f[temp2][i]; } } return f[temp1][0]; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n-1;i++) { int a,b,t; scanf("%d%d%d",&a,&b,&t); Add_Edge(a,b,t); temp[a]=1; temp1[b]=1; } for (int i=1;i<=n;i++) if (temp[i]==1&&temp1[i]==0) { root=i; break; } deep[root]=1; find_father(root,root); init_LCA(); for (int i=1;i<=m;i++) { int u1,v1; scanf("%d%d",&u1,&v1); int temp=deep[v1]-deep[u1]; if (LCA(u1,v1)==u1) { num++; int now=v1; for (int i=int(log(temp)/log(2))+1;i>=0;i--) if (temp-(1<<i)>=0) { ans+=c[now][i]; now=f[now][i]; temp=temp-(1<<i); } } } printf("%d\n%lld\n",num,ans); return 0; } -
-1
时间戳判一通即可。。要注意的是u和v的起点终点顺序是固定的
我作死去判了一下起点终点，然后就。。WA9个点
不判就ACinline void add(ll x,ll y,ll z) { poi[++cnt]=y;nxt[cnt]=f[x];v[cnt]=z;f[x]=cnt; } inline void dfs(ll x,ll val) { sum[x]=val;in[x]=++tim; for(ll i=f[x];i;i=nxt[i]) dfs(poi[i],val+v[i]); out[x]=++tim; } inline void check(ll x,ll y) { if(sum[x]>sum[y]) swap(x,y); if(in[x]<in[y]&&out[y]<out[x]) ans1++,ans2+=sum[y]-sum[x]; } int main() { scanf("%lld%lld",&n,&m); For(i,1,n-1) scanf("%lld%lld%lld",&x,&y,&z),add(x,y,z); dfs(1,0); For(i,1,m) scanf("%lld%lld",&x,&y),check(x,y); printf("%lld\n%lld",ans1,ans2); } -
-1
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 10010
using namespace std;
struct Edge{
int from,to,val;
} edge[maxn];
int dis[maxn],visit[maxn],leave[maxn],head[maxn],indegree[maxn];
int n,m,dfs_clock=0,cnt=0;
long long ans=0,time=0;
void dfs(int u,int time){
visit[u]=++dfs_clock;
dis[u]=time;
for (int i=head[u];i;i=edge[i].from){
int v=edge[i].to;
dfs(v,time+edge[i].val);
}
leave[u]=++dfs_clock;
}
int main()
{
memset(head,0,sizeof(head));
memset(dis,0,sizeof(dis));
memset(visit,0,sizeof(visit));
memset(leave,0,sizeof(leave));
memset(indegree,0,sizeof(indegree));
scanf("%d%d",&n,&m);
for (int i=1;i<n;++i){
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
edge[++cnt].to=b;edge[cnt].val=t;edge[cnt].from=head[a];head[a]=cnt;
indegree[b]++;
}
for (int i=1;i<=n;++i) if (!indegree[i]) dfs(i,0);
for (int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
if (visit[u]<visit[v]&&leave[u]>leave[v]){
++ans;
time+=dis[v]-dis[u];
}
}
printf("%I64d\n%I64d\n",ans,time);
return 0;
}
记得用long long……还有vijos的控制符是I64d…… -
-1
没想到懒惰的后果竟是这样：
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 72ms
├ 测试数据 07：答案正确... 275ms
├ 测试数据 08：答案正确... 197ms
├ 测试数据 09：答案正确... 244ms
├ 测试数据 10：答案正确... 244ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1032ms
我只记录了每个节点的父亲，每次dfs时都临时找一遍。dfs用递归写。写起来很爽，可是评测器好像累了一点 -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
额....我是第67个.... -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms链表这东西还满好的！
-
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
-2
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
program543
LV 8
@ 2017-09-29 16:51:46
