Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

为什么我写的光RE

Posted by 2944564308 at 2016-05-29 10:41:34 on Problem 2763 and last updated at 2016-05-29 10:42:51
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100001;
int dep[maxn],siz[maxn],son[maxn],top[maxn],id[maxn],fa[maxn],cnt,h[maxn],val[maxn],n,q,s,a,b,t,pos,num;
int e[maxn][3];
struct edge{
	int fr,to,next;
}edges[maxn<<1];
struct segtree{
	int l,r,val;
}tr[maxn*6];
inline void init(){
	cnt = 0;
	memset(h,-1,sizeof(h));
	memset(dep,0,sizeof(dep));
	memset(siz,0,sizeof(siz));
	memset(fa,0,sizeof(fa));
	memset(id,0,sizeof(id));
	memset(edges,0,sizeof(edge));
	memset(val,0,sizeof(val));
	memset(e,0,sizeof(e));
	memset(top,0,sizeof(top));
	memset(tr,0,sizeof(tr));
	num = 0;
}
inline void addedge(int u,int v){
	edges[cnt].fr = u;edges[cnt].to = v;edges[cnt].next = h[u];
	h[u] = cnt++;
}
void dfs1(int now,int father,int d){
	dep[now] = d;
	fa[now] = father;
	siz[now] = 1;
	son[now] = 0;
	for(int i = h[now];i != -1;i = edges[i].next){
		edge e1 = edges[i];
		if(e1.to == father)continue;
		dfs1(e1.to,now,d+1);
		siz[now] += siz[e1.to];
		if(siz[e1.to] > siz[son[now]]){
			son[now] = e1.to;
		}
	}
}
void getpos(int now,int tp){
	top[now] = tp;
	id[now] = ++num;
	if(son[now])getpos(son[now],tp);
	for(int i = h[now];i != -1;i = edges[i].next){
		edge e1 = edges[i];
		if(e1.to == son[now] || e1.to == fa[now])continue;
		getpos(e1.to,e1.to);
	}
}
void push_up(int v){
	tr[v].val = tr[v<<1].val + tr[v<<1|1].val;
}
void build(int l,int r,int now){
	tr[now].l = l;
	tr[now].r = r;
	if(l == r){
		tr[now].val = val[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l,mid,now<<1);
	build(mid+1,r,now<<1|1);
	push_up(now);
}
void update(int now,int v,int val){
	if(tr[now].l = tr[now].r){
		tr[now].val = val;
		return;
	}
	int mid = (tr[now].l + tr[now].r) >> 1;
	if(v <= mid)update(now<<1,v,val);
	else update(now<<1|1,v,val);
	push_up(now);
}
int query(int x,int l,int r){
	if (l <= tr[x].l && tr[x].r <= r){
        return tr[x].val;
    }
    int mid = (tr[x].l  + tr[x].r) >> 1;
    int ans = 0;
    if(l <= mid)ans += query(x<<1,l,r);
    if(r > mid)ans += query(x<<1|1,l,r);
    return ans;
}
int find(int u,int v){
	int ans = 0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])swap(u,v);
		ans += query(1,id[top[u]],id[u]);
		u = fa[top[u]];
	}
	if(u == v)return ans;
	if(dep[u] > dep[v])swap(u,v);
	ans += query(1,id[son[u]],id[v]);
	return ans;
}
int main(){
	while(scanf("%d%d%d",&n,&q,&s) != EOF){
		pos = s;
		init();
		for(int i = 1;i < n;++i){
			scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
			addedge(e[i][0],e[i][1]);
			addedge(e[i][1],e[i][0]);
		}
		dfs1(s,-1,1);
		getpos(s,s);
		for(int i = 1;i < n;++i){
			if(dep[e[i][0]] < dep[e[i][1]])swap(e[i][0],e[i][1]);
			val[id[e[i][0]]] = e[i][2];
		}
		build(1,n,1);
		for(int i = 1;i <= q;++i){
			scanf("%d",&t);
			if(t == 0){
				scanf("%d",&a);
				printf("%d\n",find(pos,a));
				pos = a;
			}
			else if(t == 1){
				scanf("%d%d",&a,&b);
				update(1,id[e[a][0]],b);
			}
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator