http://acm.pku.edu.cn/JudgeOnline/problem?id=1203
Код:
{$I-,S-,Q-,R-}
const
inf = '';
ouf = '';
maxn = 101000;
maxm = 1010000;
maxt = 24 * 60;
type integer = longint;
var d, num, time, arrive, last, start: array[0 .. maxn] of integer;
tow, reach, leave: array[0 .. maxm] of integer;
buf: array[0 .. 1 shl 20] of integer;
c: array[1 .. maxt, 1 .. 2] of integer;
n, len: integer;
procedure get(var t: integer);
var ch: char;
begin
read(ch); t := ord(ch) - ord('0');
read(ch); t := t * 10 + ord(ch) - ord('0');
read(ch);
end;
procedure updata;
var i, j, k, m, t1, t2: integer;
begin
readln(n); m := 0; len := 0;
for i := 1 to n do begin
start[i] := m;
readln(k);
for j := 1 to k do begin
m := m + 1;
get(t1); get(t2); leave[m] := t1 * 60 + t2 + 1;
get(t1); get(t2); reach[m] := t1 * 60 + t2 + 1;
if reach[m] > len then len := reach[m];
readln(tow[m]);
end;
last[i] := m;
end;
end;
var temp: integer;
procedure swap(var i, j: integer);
begin
temp := i; i := j; j := temp;
end;
procedure keepup(k: integer);
begin
while (k > 1) and (arrive[d[k]] < arrive[d[k shr 1]]) do begin
swap(d[k], d[k shr 1]);
num[d[k]] := k;
num[d[k shr 1]] := k shr 1;
k := k shr 1;
end;
end;
procedure keepdown(t: integer);
var now, p: integer;
begin
now := 0;
while (t shl 1 <= len) and (now <> t) do begin
now := t; p := now shl 1;
if arrive[d[p]] < arrive[d[t]] then t := p; p := p + 1;
if (p <= len) and (arrive[d[p]] < arrive[d[t]]) then t := p;
if now <> t then begin
swap(d[now], d[t]);
num[d[now]] := now;
num[d[t]] := t;
end;
end;
end;
procedure print(t: integer);
var k: integer;
begin
k := (t - 1) div 60; t := t - k * 60 - 1;
if k < 10 then write(0, k) else write(k); write(':');
if t < 10 then write(0, t) else write(t); write(' ');
end;
procedure main;
var u, v, ans, nowtime: integer;
begin
ans := 0;
fillchar(time, sizeof(time), 0);
for nowtime := maxt downto 1 do begin
len := 1; d[1] := 1; num[1] := 1;
time[1] := nowtime; arrive[1] := nowtime;
while len > 0 do begin
u := d[1]; len := len - 1;
if len > 0 then begin
d[1] := d[len + 1];
num[d[1]] := 1;
keepdown(1);
end;
while (start[u] < last[u]) and (leave[last[u]] >= arrive[u]) do begin
v := tow[last[u]];
if time[v] <> nowtime then begin
time[v] := nowtime;
arrive[v] := reach[last[u]];
len := len + 1;
d[len] := v; num[v] := len;
keepup(len);
end else if reach[last[u]] < arrive[v] then begin
arrive[v] := reach[last[u]];
keepup(num[v]);
end;
last[u] := last[u] - 1;
end;
end;
if time[n] = nowtime then begin
ans := ans + 1;
c[ans, 1] := nowtime;
c[ans, 2] := arrive[n];
end;
end;
if ans = 0 then writeln(0) else begin
v := ans; ans := 1;
for u := 2 to v do
if c[u, 2] < c[ans, 2] then begin
ans := ans + 1;
c[ans] := c[u];
end;
writeln(ans);
for u := ans downto 1 do begin
print(c[u, 1]);
print(c[u, 2]);
writeln;
end;
end;
end;
begin
assign(input, inf); assign(output, ouf);
settextbuf(input, buf);
reset(input); rewrite(output);
updata;
main;
close(input); close(output);
end.