# 1455: 罗马游戏

## 1455: 罗马游戏

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 721  Solved: 272

[Submit][Status][Discuss]

## 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

10 100 0 66

## Source

1 /**************************************************************
2     Problem: 1455
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:4028 ms
7     Memory:35384 kb
8 ****************************************************************/
9
10 var
11    i,j,k,l,m,n:longint;
12    a,lef,rig,fix,fat,mak:array[0..1500000] of longint;
13    ch:char;
14 function min(x,y:longint):longint;
15          begin
16               if x<y then min:=x else min:=y;
17          end;
18 function max(x,y:longint):longint;
19          begin
20               if x>y then max:=x else max:=y;
21          end;
22 procedure swap(var x,y:longint);
23           var z:longint;
24           begin
25                z:=x;x:=y;y:=z;
26           end;
27 procedure merge(var x,y:longint);
28           begin
29                if x=0 then
30                   begin
31                        fat[y]:=fat[x];fat[x]:=0;
32                        swap(x,y);
33                   end;
34                if y=0 then exit;
35                if a[y]<a[x] then
36                   begin
37                        fat[y]:=fat[x];fat[x]:=0;
38                        swap(x,y);
39                   end;
40                merge(rig[x],y);
41                fat[rig[x]]:=x;
42                fix[x]:=min(fix[lef[x]],fix[rig[x]])+1;
43                if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);
44           end;
45 function getfat(x:longint):longint;
46          begin
47               while fat[x]<>0 do x:=fat[x];
48               exit(x);
49          end;
50 begin
52      fillchar(lef,sizeof(lef),0);
53      fillchar(rig,sizeof(rig),0);
54      fillchar(fix,sizeof(fix),0);
55      fillchar(fat,sizeof(fat),0);
56      fillchar(mak,sizeof(mak),0);
57      for i:=1 to n do read(a[i]);
60      for i:=1 to m do
61          begin
63               case upcase(ch) of
64                    'M':begin
66                             if (mak[j]=1) or (mak[k]=1) then continue;
67                             j:=getfat(j);k:=getfat(k);
68                             if j=k then continue;
69                             merge(j,k);
70                    end;
71                    'K':begin
73                             if mak[j]=1 then
74                                begin
75                                     writeln(0);
76                                     continue;
77                                end;
78                             j:=getfat(j);
79                             mak[j]:=1;
80                             writeln(a[j]);
81                             merge(lef[j],rig[j]);
82                             j:=lef[j];
83                             fat[j]:=0;
84                    end;
85               end;
86          end;
88 end.

0 条评论

## 相关文章

2248

2573

701

### Android游戏开发十日通（6）- 太空大战

http://blog.csdn.net/silangquan/article/details/16921035

1212

4768

### 聊聊lettuce的指标监控

lettuce-core-5.0.4.RELEASE-sources.jar!/io/lettuce/core/event/metrics/DefaultCom...

2592

### Microservices Ecosystem Transit Map

…we assembled a map of the ecosystem to help guide practitioners, vendors, inves...

3794

3332

1353

2255