| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 115795 |
2019-06-09T07:25:10 Z |
maho04 |
허수아비 (JOI14_scarecrows) |
C++14 |
|
0 ms |
0 KB |
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.}
Compilation message
scarecrows.cpp:1:3: error: stray '#' in program
1.#include <bits/stdc++.h>
^
scarecrows.cpp:2:3: error: stray '#' in program
2.#define x first
^
scarecrows.cpp:3:3: error: stray '#' in program
3.#define y second
^
scarecrows.cpp:1:1: error: expected unqualified-id before numeric constant
1.#include <bits/stdc++.h>
^~
scarecrows.cpp:5:1: error: expected unqualified-id before numeric constant
5.
^~
scarecrows.cpp:7:1: error: expected unqualified-id before numeric constant
7.typedef pair<int, int> p;
^~~~~~~~~
scarecrows.cpp:8:1: error: expected unqualified-id before numeric constant
8.
^~
scarecrows.cpp:10:1: error: expected unqualified-id before numeric constant
10.const int dx[] = {1, -1, 0, 0};
^~~~~~~~
scarecrows.cpp:11:1: error: expected unqualified-id before numeric constant
11.const int dy[] = {0, 0, 1, -1};
^~~~~~~~
scarecrows.cpp:12:1: error: expected unqualified-id before numeric constant
12.
^~~
scarecrows.cpp:14:1: error: expected unqualified-id before numeric constant
14.int chk[101010];
^~~~~~
scarecrows.cpp:15:1: error: expected unqualified-id before numeric constant
15.int n;
^~~~~~
scarecrows.cpp:16:1: error: expected unqualified-id before numeric constant
16.map<p, int> mp;
^~~~~~
scarecrows.cpp:17:1: error: expected unqualified-id before numeric constant
17.set<int> g[101010];
^~~~~~
scarecrows.cpp:18:1: error: expected unqualified-id before numeric constant
18.
^~~
scarecrows.cpp:31:1: error: expected unqualified-id before numeric constant
31.
^~~
scarecrows.cpp:38:1: error: expected unqualified-id before numeric constant
38.
^~~
scarecrows.cpp:68:1: error: expected unqualified-id before numeric constant
68.
^~~
