【bzoj1455】罗马游戏
2024-09-07 18:57:30
1455: 罗马游戏
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1061 Solved: 439
[Submit][Status][Discuss]
Description
罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人,每个人都是一个独立的团。最近举行了一次平面几何测试,每个人都得到了一个分数。 皇帝很喜欢平面几何,他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令: 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人,那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了,这条命令就忽略。 皇帝希望他每发布一条kill命令,下面的将军就把被杀的人的分数报上来。(如果这条命令被忽略,那么就报0分)
Input
第一行一个整数n(1<=n<=1000000)。n表示士兵数,m表示总命令数。 第二行n个整数,其中第i个数表示编号为i的士兵的分数。(分数都是[0..10000]之间的整数) 第三行一个整数m(1<=m<=100000) 第3+i行描述第i条命令。命令为如下两种形式: 1. M i j 2. K i
Output
如果命令是Kill,对应的请输出被杀人的分数。(如果这个人不存在,就输出0)
Sample Input
5
100 90 66 99 10
7
M 1 5
K 1
K 1
M 2 3
M 3 4
K 5
K 4
100 90 66 99 10
7
M 1 5
K 1
K 1
M 2 3
M 3 4
K 5
K 4
Sample Output
10
100
0
66
100
0
66
左偏树裸题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,a[],f[],die[],r[],l[],dist[];
inline int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int merge(int x,int y)
{
if(!x) return y;
if(!y) return x;
if(a[x]>a[y]) swap(x,y);
r[x]=merge(r[x],y);
if(dist[r[x]]>dist[l[x]]) swap(r[x],l[x]);
dist[x]=dist[r[x]]+;
return x;
}
int main()
{
freopen("cin.in","r",stdin);
freopen("cout.out","w",stdout);
n=read();
for(int i=;i<=n;i++) {a[i]=read(); f[i]=i;}
m=read(); dist[]=-;
for(int i=;i<=m;i++)
{
char ch=getchar();
if(ch=='M')
{
int x=read(),y=read();
if(die[x]||die[y]) continue;
x=find(x); y=find(y);
if(x!=y)
{
int t=merge(x,y);
f[x]=f[y]=t;
}
}
else
{
int x=read();
if(die[x]) printf("0\n");
else
{
x=find(x); die[x]=;
printf("%d\n",a[x]);
f[x]=merge(l[x],r[x]);
f[f[x]]=f[x];
}
}
}
return ;
}
最新文章
- 14 Generator
- 个人博客作业week7
- Discrete.Differential.Geometry-An.Applied.Introduction(sig2008)笔记
- JAVA序列化的作用
- PHP之MVC项目实战(三)
- Redis过期时间
- SqlServer2008快照隔离模式的业务应用
- 怎么在官网下载jstl【配图详解】
- System V 消息队列
- 自定义key解决zabbix端口监听取值不准确的问题
- Python之路:Python简介
- WebRequest调用
- Python基础学习篇章四
- ASP.NET Core 下自定义权限验证
- 【微服务No.4】 API网关组件Ocelot+Consul
- [转帖]SAP一句话入门:Plant Maintenance
- C与C++的部分区别
- java和python中的string和int数据类型的转换
- 简单地说, cpp中的纯虚函数就是抽象类的具体实现
- 各JAVA开发框架版本及对应信息
热门文章
- 看过自会理解, Photon Server 常见概念分析.
- 【Java 并发】Executor框架机制与线程池配置使用
- (六)js常见四大排序
- (二)Vue常用7个属性
- session不一定非得要cookie开启才能使用。也可以使用get传递参数
- Microsoft office2007免费版下载(安装 + 破解)
- Java Platform SE binary已停止运行 Can't load AMD 64-bit.dll on a IA 32-bit platform错误
- JS、Jquery获取浏览器和屏幕各种高度宽度
- spark-shell与scala生成parquet文件
- Android中内容观察者的使用---- ContentObserver类详解 (转)