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:这题卡的太紧了啊,G++跑了TLE怎么搞都不好,换C++跑了3.9s,代码

Posted by 1507010109 at 2017-01-29 17:33:03 on Problem 2763
In Reply To:这题卡的太紧了啊,G++跑了TLE怎么搞都不好,换C++跑了3.9s,代码 Posted by:lonelam at 2016-12-01 22:04:04
> #define _CRT_SECURE_NO_WARNINGS
> #include<algorithm>
> #include<vector>
> #include<cstdio>
> #include<cstring>
> #include<queue>
> using namespace std;
> const int maxn = 330001 * 2;
> //BIT implemention
> int sum_n;
> int C[maxn];
> int lsb(int x)
> {
> 	return x&(-x);
> }
> int sum(int x)
> {
> 	int ret = 0;
> 	while (x > 0)
> 	{
> 		ret += C[x];
> 		x -= lsb(x);
> 	}
> 	return ret;
> }
> void add(int x, int d)
> {
> 	while (x <= sum_n)
> 	{
> 		C[x] += d;
> 		x += lsb(x);
> 	}
> }
> void sum_init(int N)
> {
> 	sum_n = 1;
> 	while (N > sum_n)
> 	{
> 		sum_n <<= 1;
> 	}
> 	sum_n <<= 1;
> 	memset(C, 0, sizeof(int) * sum_n);
> }
> struct edge
> {
> 	int to, cost, id;
> 	edge() {}
> 	edge(int to, int cost, int id) : to(to), cost(cost), id(id) {}
> };
> int k;
> int vs[maxn * 2];
> vector<int> G[maxn];
> int sz;
> edge es[maxn * 2 + 20 ];
> ///LCA RMQ version!!
> const int inf = 0x3f3f3f3f;
> void add_edge(int from, int to, int weight, int id)
> {
> 	G[from].push_back(sz);
> 	es[sz].to = to;
> 	es[sz].id = id;
> 	es[sz++].cost = weight;
> 	G[to].push_back(sz);
> 	es[sz].to = from;
> 	es[sz].id = id;
> 	es[sz++].cost = weight;
> }
> ///RMQ !
> 
> int RMQ[maxn * 2 + 1];
> int RMQ_N;
> void rmq_init(int * tar, int n)
> {
> 	RMQ_N = 1;
> 	while (n > RMQ_N)
> 	{
> 		RMQ_N <<= 1;
> 	}
> 	RMQ_N <<= 1;
> 	for (int i = 0; i < n; i++)
> 	{
> 		RMQ[RMQ_N + i] = i;
> 	}
> 	for (int i = n; i < RMQ_N; i++)
> 	{
> 		RMQ[RMQ_N + i] = -1;
> 	}
> 	for (int i = RMQ_N - 1; i > 0; i--)
> 	{
> 		if (RMQ[i * 2] == -1)
> 		{
> 			RMQ[i] = RMQ[i * 2 + 1];
> 		}
> 		else if (RMQ[i * 2 + 1] == -1 ||tar[RMQ[i * 2]] < tar[RMQ[i * 2 + 1]])
> 		{
> 			RMQ[i] = RMQ[i * 2];
> 		}
> 		else
> 		{
> 			RMQ[i] = RMQ[i * 2 + 1];
> 		}
> 	}
> }
> int depth[maxn * 2 + 1];
> int inner_query(int l, int r, int o, int ql, int qr)
> {
> 	if (ql <= l && r <= qr)
> 	{
> 		return RMQ[o];
> 	}
> 	if (r < ql || qr < l)
> 	{
> 		return -1;
> 	}
> 	int ans = 0;
> 	const int mid = l + (r - l) / 2;
> 	int dl = inner_query(l, mid, o * 2, ql, qr);
> 	int dr = inner_query(mid + 1, r, o * 2 + 1, ql, qr);
> 	if (dl == -1)
> 	{
> 		return dr;
> 	}
> 	if (dr == -1 || depth[dl] < depth[dr])
> 	{
> 		return dl;
> 	}
> 	else
> 	{
> 		return dr;
> 	}
> }
> int query(int l, int r)
> {
> 	return inner_query(0, RMQ_N - 1, 1, l, r);
> }
> ///LCA
> int id_access1[maxn];
> int id_access2[maxn];
> int id_w[maxn];
> int fp[maxn];
> void dfs(int u, int p, int d)
> {
> 	depth[k] = d;
> 	fp[u] = k;
> 	vs[k++] = u;
> 	for (int i = 0; i < G[u].size(); i++)
> 	{
> 		edge & e = es[G[u][i]];
> 		if (e.to != p)
> 		{
> 			add(k, e.cost);
> 			id_access1[e.id] = k;
> 			dfs(e.to, u, d + 1);
> 			add(k, -e.cost);
> 			id_access2[e.id] = k;
> 			depth[k] = d;
> 			vs[k++] = u;
> 		}
> 	}
> }
> int lca(int ll, int rr)
> {
> 	return fp[vs[query(ll, rr)]];
> }
> int main()
> {
> 	int V, q, s;
> 	int from, to, cost;
> 
> 	while (scanf("%d%d%d", &V, &q, &s)!=EOF)
> 	{
> 		sz = 0;
> 		k = 1;
> 		sum_init(V * 2 + 1);
> 		for (int i = 1; i <= V ; i++)
> 		{
> 			G[i].clear();
> 		}
> 
> 		for (int i = 1; i < V; i++)
> 		{
> 			scanf("%d%d%d", &from, &to, &cost);
> 			add_edge(from, to, cost, i);
> 			id_w[i] = cost;
> 		}
> 		dfs(s, -1, 0);
> 		rmq_init(depth, k);
> 		int cur = s;
> 		int cmd;
> 		int u;
> 		int nno, wto;
> 		for (int i = 0; i < q; i++)
> 		{
> 			scanf("%d", &cmd);
> 			if (cmd == 0)
> 			{
> 				scanf("%d", &u);
> 				int l = min(fp[cur], fp[u]);
> 				int r = max(fp[cur], fp[u]);
> 				printf("%d\n", sum(l) + sum(r) - 2 * sum(lca(l, r)));
> 				cur = u;
> 			}
> 			else
> 			{
> 				scanf("%d%d", &nno, &wto);
> 				add(id_access1[nno], wto - id_w[nno]);
> 				add(id_access2[nno], id_w[nno] - wto);
> 				id_w[nno] = wto;
> 			}
> 		}
> 	}
> }
> 
> /*
> 
> 10 40 5
> 1 2 4
> 1 3 3
> 1 4 1
> 4 5 9
> 5 6 6
> 4 7 6
> 1 8 2
> 1 9 7
> 9 10 3
> 0 1
> 1 6 9
> 1 7 2
> 0 6
> 
> 
> */

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