# 3522: [Poi2014]Hotel

## 3522: [Poi2014]Hotel

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 253  Solved: 117

[Submit][Status][Discuss]

## Sample Input

7 1 2 5 7 2 5 2 3 5 6 4 5

5

## HINT

【样例解释】 {1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}

【数据范围】 n≤5000

## Source

By Dzy

  1 /**************************************************************
2     Problem: 3522
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:7828 ms
7     Memory:3316 kb
8 ****************************************************************/
9
10 type
11     point=^node;
12     node=record
13                g,w:longint;
14                next:point;
15     end;
16     map=array[0..20000] of point;
17 var
18    i,j,k,l,m,n:longint;
19    a,c:map;
20    b:array[0..20000] of int64;
21    d,e,f,g:array[0..20000] of longint;
22    p:point;
23    ans:int64;
25           var p:point;
26           begin
27                new(p);p^.g:=y;p^.w:=z;
28                p^.next:=a[x];a[x]:=p;
29           end;
30 function cal:int64;
31          var i:longint;a1,a2,a3:int64;
32          begin
33               a1:=0;a2:=0;a3:=0;
34               if b[0]<3 then exit(0);
35               for i:=1 to b[0] do
36                   begin
37                        a1:=a1+b[i];
38                        a2:=a2+b[i]*b[i];
39                        a3:=a3+b[i]*b[i]*b[i];
40                   end;
41               exit((a1*a1*a1-3*a1*a2+2*a3) div 6);
42          end;
43 procedure dfs(x,y:longint);
44           var p:point;
45           begin
46                p:=a[x];g[x]:=1;
47                while p<>nil do
48                      begin
49                           if g[p^.g]=0 then
50                              begin
51                                   inc(d[y+1]);
52                                   dfs(p^.g,y+1);
53                              end;
54                           p:=p^.next;
55                      end;
56           end;
57 begin
59      for i:=1 to n do a[i]:=nil;
60      for i:=1 to n-1 do
61          begin
64          end;
65      ans:=0;
66      for i:=1 to n do
67          begin
68               p:=a[i];
69               for j:=1 to n do c[j]:=nil;
70               fillchar(g,sizeof(g),0);
71               g[i]:=1;
72               while p<>nil do
73                     begin
74                          fillchar(d,sizeof(d),0);
75                          d[1]:=1;
76                          dfs(p^.g,1);
77                          for j:=1 to n do
78                              begin
79                                   if d[j]=0 then break;
81                              end;
82                          p:=p^.next;
83                     end;
84               for j:=1 to n do
85                   begin
86                        b[0]:=0;
87                        p:=c[j];
88                        while p<>nil do
89                              begin
90                                   inc(b[0]);
91                                   b[b[0]]:=p^.g;
92                                   p:=p^.next;
93                              end;
94                        inc(ans,cal);
95                   end;
96
97               j:=0;
98          end;
99      writeln(ans);
101 end.                      

0 条评论

• ### 2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

• ### 1131: [POI2008]Sta

1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 783  Solved:...

• ### 算法模板——sap网络最大流 2（非递归+邻接表）

实现功能：同最大流 1 这里面主要是把前面的邻接矩阵改成了邻接表，相比之下速度大大提高——本人实测，当M=1000000 N=10000 时，暂且不考虑邻接矩阵...

• ### 算法模板——计算几何2（二维凸包——Andrew算法）

实现功能：求出二维平面内一对散点的凸包（详见Codevs 1298） 很神奇的算法——先将各个点按坐标排序，然后像我们所知的那样一路左转，求出半边的凸包，然后反...

• ### 1601: [Usaco2008 Oct]灌水

1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

• ### 1015: [JSOI2008]星球大战starwar

1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MB Submit: 3001...

• ### 【kafka】kafka学习笔记（一）

我们先看一下维基百科是怎么说的： Kafka是由Apache软件基金会开发的一个开源流处理平台，由Scala和Java编写。该项目的目标是为处理实时数据提供一...

• ### 4052: [Cerc2013]Magical GCD

4052: [Cerc2013]Magical GCD Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 148...

• ### react组件性能优化探索实践

React本身就非常关注性能，其提供的虚拟DOM搭配上Diff算法，实现对DOM操作最小粒度的改变也是非常的高效。然而其组件渲染机制，也决定了在对组件进行更新时...

• ### react组件性能优化探索实践

React本身就非常关注性能，其提供的虚拟DOM搭配上Diff算法，实现对DOM操作最小粒度的改变也是非常的高效。然而其组件渲染机制，也决定了在对组件进行更新时...