hdu 3974 Assign the task (线段树+树的遍历)
Description
The company usually assigns some tasks to some employees to finish.When a task is assigned to someone,He/She will assigned it to all his/her subordinates.In other words,the person and all his/her subordinates received a task in the same time. Furthermore,whenever a employee received a task,he/she will stop the current task(if he/she has) and start the new one.
Write a program that will help in figuring out some employee’s current task after the company assign some tasks to some employee.
Input
For each test case:
The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.
The following N - 1 lines each contain two integers u and v, which means the employee v is the immediate boss of employee u(1<=u,v<=N).
The next line contains an integer M (M ≤ 50,000).
The following M lines each contain a message which is either
"C x" which means an inquiry for the current task of employee x
or
"T x y"which means the company assign task y to employee x.
(1<=x<=N,0<=y<=10^9)
Output
Sample Input
1
5
4 3
3 2
1 3
5 2
5
C 3
T 2 1
C 3
T 3 2
C 3
Sample Output
Case #1:
-1
1
2 代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = ;
int n,Q,t,topboss,cnt;
int head[MAXN],tot;
int start[MAXN],endd[MAXN];
bool used[MAXN];
struct Edge
{
int to,next;
}edge[MAXN];
void init()
{
cnt=;
tot=;
memset(head,-,sizeof head);
memset(used,false,sizeof used);
}
void addedge (int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void dfs(int u)
{
++cnt;
start[u]=cnt;
for (int i=head[u];i!=-;i=edge[i].next)
{
dfs(edge[i].to);
}
endd[u]=cnt;
}
struct Node
{
int l,r,val,lazy;
}segTree[MAXN<<];
void upDate_Same (int r,int v)
{
if (r)
{
segTree[r].val=v;
segTree[r].lazy=;
}
}
void push_down (int r)
{
if (segTree[r].lazy)
{
upDate_Same(r<<,segTree[r].val);
upDate_Same(r<<|,segTree[r].val);
segTree[r].lazy=;
}
}
void buildTree (int i,int l,int r)
{
segTree[i].l=l;
segTree[i].r=r;
segTree[i].val=-;
segTree[i].lazy=;
if (l==r)
return ;
int mid =(l+r)>>;
buildTree(i<<,l,mid);
buildTree(i<<|,mid+,r);
}
void update (int i,int l,int r,int v)
{
if (segTree[i].l==l&&segTree[i].r==r)
{
upDate_Same(i,v);
return ;
}
push_down(i);
int mid =(segTree[i].l+segTree[i].r)/;
if (r<=mid) update(i<<,l,r,v);
else if (l>mid) update(i<<|,l,r,v);
else
{
update(i<<,l,mid,v);
update(i<<|,mid+,r,v);
}
}
int query (int i,int u)
{
if (segTree[i].l==u&&segTree[i].r==u)
return segTree[i].val;
push_down(i);
int mid =(segTree[i].l+segTree[i].r)/;
if (u<=mid)
return query(i<<,u);
else
return query(i<<|,u);
}
int main()
{
//freopen("de.txt","r",stdin);
cin>>t;
int casee=;
while (t--){
printf("Case #%d:\n",++casee);
int u,v;
init();
scanf("%d",&n);
for (int i=;i<n-;++i){
cin>>u>>v;
used[u]=true;
addedge(v,u);
}
for (int i=;i<=n;++i){
if (!used[i]){
dfs(i);
break;
}
}
cin>>Q;
buildTree(,,cnt);
char op[];
while (Q--){
scanf("%s",op);
if (op[]=='C'){
scanf("%d",&u);
printf("%d\n",query(,start[u]));
}
else{
scanf("%d%d",&u,&v);
update(,start[u],endd[u],v);
}
}
}
return ;
}
700ms,有人200ms过了,正在研究。http://vjudge.net/contest/source/7108995 http://vjudge.net/contest/source/6308790
最新文章
- HTTP缓存
- MySQL索引的Index method中btree和hash的优缺点
- 第13章 .NET应用程序配置
- android之自定义广播
- SPOJ913 Query on a tree II
- HTML5:离线存储(缓存机制)-IndexDB
- mysql insert一条记录后怎样返回创建记录的主键id,last_insert_id(),selectkey
- 【转】使用git、git-flow与gitlab工作
- Android SDK 更新镜像服务器
- 在SQL中取出字符串中数字部分或在SQL中取出字符部分
- ruby cookbook
- 2014-9-17二班----6 web project
- MHA工作原理
- LabVIEW设计模式系列——资源关闭后错误处理
- android中发送邮件
- 蚂蚁的难题(二)首尾相连数组的最大子数组和(DP)
- OpenGL Development Cookbook chapter7部分翻译
- 大数据之HBase
- DeepLearning.ai学习笔记(四)卷积神经网络 -- week3 目标检测
- 6 个开源的家庭自己主动化工具 | Linux 中国
热门文章
- springMVC使用map接收入参 + mybatis使用map 传入查询参数
- 图与例解读Async/Await
- 连载 3:利用 matlab计算卷积
- HihoCoder - 1673 (单调队列)
- bugku | sql注入2
- [CSP-S模拟测试]:联(小清新线段树)
- winform防止输入法对扫码的干扰
- 【SpringBoot】 理解Spirng中的IOC原理
- 102.kaldi 斯坦福语音识别工具的编译
- 用 Flask 来写个轻博客 (31) — 使用 Flask-Admin 实现 FileSystem 管理