| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 115795 | maho04 | 허수아비 (JOI14_scarecrows) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
1.#include <bits/stdc++.h>
2.#define x first
3.#define y second
4.using namespace std;
5.
6.typedef long long ll;
7.typedef pair<int, int> p;
8.
9.const int mod = 1e9;
10.const int dx[] = {1, -1, 0, 0};
11.const int dy[] = {0, 0, 1, -1};
12.
13.int size[101010];
14.int chk[101010];
15.int n;
16.map<p, int> mp;
17.set<int> g[101010];
18.
19.void dfs(int now, int prv, ll &dist){
20. for(auto nxt : g[now]){
21. if(nxt ^ prv && !chk[nxt]){
22. chk[nxt] = 1;
23. dfs(nxt, now, dist);
24. size[now] += size[nxt];
25. }
26. }
27. ll tmp = (ll)size[now] * (ll)(n - size[now]);
28. tmp %= mod;
29. dist += tmp; dist %= mod;
30.}
31.
32.ll getDist(){
33. ll ret = 0;
34. chk[1] = 1;
35. dfs(1, 0, ret);
36. return ret;
37.}
38.
39.void makeTree(vector<p> &v){
40. sort(v.begin()+1, v.end());
41. memset(size, 0, sizeof size);
42. memset(chk, 0, sizeof chk);
43. for(int i=0; i<=n; i++) g[i].clear();
44. mp.clear();
45.
46. int cnt = 1;
47. mp[v[1]] = cnt;
48. size[cnt]++;
49. for(int i=2; i<=n; i++){
50. if(v[i-1].x == v[i].x && v[i-1].y+1 == v[i].y){
51. mp[v[i]] = cnt;
52. }
53. else mp[v[i]] = ++cnt;
54. size[cnt]++;
55. }
56.
57. for(int i=1; i<=n; i++){
58. int x = v[i].x, y = v[i].y;
59. int now = mp[v[i]];
60. for(int k=0; k<4; k++){
61. int xx = x + dx[k];
62. int yy = y + dy[k];
63. int nxt = mp[{xx, yy}];
64. if(nxt && now != nxt) g[now].insert(nxt);
65. }
66. }
67.}
68.
69.int DistanceSum(int N, int *X, int *Y){
70. n = N;
71. ll ret = 0;
72. vector<p> v(n+1);
73. for(int i=0; i<n; i++){
74. v[i+1] = {X[i], Y[i]};
75. }
76. makeTree(v);
77. ret += getDist() % mod;
78.
79. for(int i=0; i<n; i++){
80. v[i+1] = {Y[i], X[i]};
81. }
82. makeTree(v);
83. ret += getDist() % mod;
84. ret %= mod;
85. return (int)ret;
86.}