### 比赛地址

### A. Photo of The Sky

#### Statement

There is a beautiful garden of stones in Innopolis.

Its most beautiful place is the n piles with stones numbered from $n$.

EJOI participants have visited this place twice.

When they first visited it, the number of stones in piles was $x_1, x_2, ldots, x_n$, correspondingly. One of the participants wrote down this sequence in a notebook.

They visited it again the following day, and the number of stones in piles was equal to $y_1, y_2, ldots, y_n$. One of the participants also wrote it down in a notebook.

It is well known that every member of the EJOI jury during the night either sits in the room $108$ or comes to the place with stones. Each jury member who comes there either takes one stone for himself or moves one stone from one pile to another. We can assume that there is an unlimited number of jury members. No one except the jury goes to the place with stones at night.

Participants want to know whether their notes can be correct or they are sure to have made a mistake.

#### I/O

##### Input

The first line of the input file contains a single integer $n$, the number of piles with stones in the garden $1 leq n leq 50$.

The second line contains n integers separated by spaces $x_1, x_2, ldots, x_n$, the number of stones in piles recorded in the notebook when the participants came to the place with stones for the first time ($0 leq x_i leq 1000$).

The third line contains $n$ integers separated by spaces $y_1, y_2, ldots, y_n$, the number of stones in piles recorded in the notebook when the participants came to the place with stones for the second time ($0 leq y_i leq 1000$).

##### Output

If the records can be consistent output “Yes”, otherwise output “No” (quotes for clarity).

#### Sample

##### Input

1 2 3 |
5 1 1 1 1 1 1 0 1 0 1 |

##### Output

1 |
Yes |

#### Idea

首先我们对给定的序列排个序。

我们要使矩形面积尽量小，那么我们不妨从序列中选取连续的 $n$ 个数作为不同点的横坐标。可以证明~~（我才不证明给你看呢）~~这是科学的，因为通过交换数字使序列不连续不会使答案变优。

所以我们可以 $O(n)$ 枚举选出的连续横坐标序列的最小值，$O(1)$ 计算对于每一个位置的答案。

#### Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <bits/stdc++.h> #define maxn 100010 #define ll long long #define INF 1e18+5 using namespace std; int a[maxn<<1],n; ll ans=INF; int main(){ ios::sync_with_stdio(false); cin>>n; for (int i=1;i<=2*n;i++) cin>>a[i]; sort(a+1,a+1+2*n); for (int l=1;l<=n;l++){ ll wid=a[l+n-1]-a[l]; ll het=a[2*n]-a[(l==1?n+1:1)]; ans=min(ans,wid*het); } cout<<ans<<endl; } |

### B. Chemical table

#### Statement

Innopolis University scientists continue to investigate the periodic table. There are *n*·*m* known elements and they form a periodic table: a rectangle with *n* rows and *m* columns. Each element can be described by its coordinates (*r*, *c*) (1 ≤ *r* ≤ *n*, 1 ≤ *c* ≤ *m*) in the table.

Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions (*r*_{1}, *c*_{1}), (*r*_{1}, *c*_{2}), (*r*_{2}, *c*_{1}), where *r*_{1} ≠ *r*_{2} and *c*_{1} ≠ *c*_{2}, then we can produce element (*r*_{2}, *c*_{2}).

Samples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions.

Innopolis University scientists already have samples of *q* elements. They want to obtain samples of all *n*·*m* elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.

#### I/O

##### Input

The first line contains three integers *n*, *m*, *q* (1 ≤ *n*, *m* ≤ 200 000; 0 ≤ *q* ≤ *min*(*n*·*m*, 200 000)), the chemical table dimensions and the number of elements scientists already have.

The following *q* lines contain two integers *r*_{i}, *c*_{i} (1 ≤ *r*_{i} ≤ *n*, 1 ≤ *c*_{i} ≤ *m*), each describes an element that scientists already have. All elements in the input are different.

##### Output

Print the minimal number of elements to be purchased.

#### Sample

##### Input

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

##### Output

1 |
1 |

##### Note

There are several possible solutions. One of them is illustrated below.

Note that after purchasing one element marked as red it’s still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.

#### Idea

我们用二分图建图即可。

二分图中节点为行号和列号，对于原图中存在的点，连接二分图中的行号和列号。我们发现每三个满足条件的节点连边后会形成一个联通块。我们要填满原图，就是让原图形成一个联通块，那么需要购买的元素就是联通块数量减一。

#### Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// Chemical_table.cpp : Defines the entry point for the console application. // XG_Zepto, 7/31/2018. All rights reserved. #include "stdafx.h" #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 200100 using namespace std; struct Edge{ int to,next; Edge(int a=0,int b=0){ to=a,next=b; } }l[maxn<<2]; int head[maxn<<1],m,cnt,n,q,ans,vis[maxn<<1]; void Add(int a,int b){ l[++cnt]=Edge(b,head[a]); head[a]=cnt; } void Dfs(int u){ vis[u]=1; for(int i=head[u];i;i=l[i].next){ if (!vis[l[i].to]) Dfs(l[i].to); } } int main(){ ios::sync_with_stdio(false); cin>>n>>m>>q; for(int i=1;i<=q;i++){ int x,y; cin>>x>>y; Add(x,y+n); Add(y+n,x); } for (int i=1;i<=n+m;i++) if (!vis[i]) Dfs(i),ans++; cout<<ans-1<<endl; system("PAUSE"); return 0; } |