Submission #466359

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
466359	2021-08-19 00:11:19	training4usaco	Fancy Fence (CEOI20_fancyfence)	C++11	100 / 100	44 ms	6248 KiB

fancyfence

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
 
const int LIM = 1e5+1, MOD = 1e9+7;
 
int n, h[LIM], w[LIM], e[LIM], dp[LIM];
 
int nC2(int x){ return ((x * (x-1)) / 2) % MOD; }
 
int cnt(int x, int y){
  return (nC2(x+1) * nC2(y+1)) % MOD;
}
 
int find(int u){
  return e[u] < 0 ? u : e[u] = find(e[u]);
}
 
void unite(int u, int v, int currH){
  u = find(u), v = find(v);
  if(u != v){
    if(e[u] > e[v]) swap(u, v);
    dp[u] += cnt(w[u], h[u]) - cnt(w[u], currH);
    dp[v] += cnt(w[v], h[v]) - cnt(w[v], currH);
 
    e[u] += e[v], e[v] = u;
    (w[u] += w[v]) %= MOD;
    (dp[u] += dp[v]) %= MOD;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27