# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
118445 |
2019-06-19T03:46:26 Z |
E869120 |
Ideal city (IOI12_city) |
C++14 |
|
766 ms |
24244 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
long long N, X[100009], Y[100009], col[100009], cnt[100009], rem, dp[100009]; bool used[100009];
long long ans, mod = 1000000000;
vector<int>G[100009];
void dfs1(int pos, long long dep) {
used[pos] = true;
rem += dep * cnt[pos]; dp[pos] = cnt[pos];
for (int i = 0; i < G[pos].size(); i++) {
if (used[G[pos][i]] == true) continue;
dfs1(G[pos][i], dep + 1);
dp[pos] += dp[G[pos][i]];
}
}
void dfs2(int pos) {
ans += 1LL * cnt[pos] * rem; used[pos] = true;
for (int i = 0; i < G[pos].size(); i++) {
if (used[G[pos][i]] == true) continue;
rem -= (dp[G[pos][i]]) - (N - dp[G[pos][i]]);
dfs2(G[pos][i]);
rem += (dp[G[pos][i]]) - (N - dp[G[pos][i]]);
}
}
long long solve() {
rem = 0; ans = 0;
for (int i = 0; i <= N; i++) { G[i].clear(); col[i] = 0; cnt[i] = 0; dp[i] = 0; used[i] = false; }
vector<tuple<int, int, int>>vec;
map<pair<int, int>, int>Map;
for (int i = 0; i < N; i++) {
Map[make_pair(X[i], Y[i])] = i + 1;
vec.push_back(make_tuple(X[i], Y[i], i));
}
sort(vec.begin(), vec.end());
int cnts = 0;
for (int i = 0; i < vec.size(); i++) {
if (col[get<2>(vec[i])] >= 1) continue;
int ex = get<0>(vec[i]), ey = get<1>(vec[i]); cnts++;
int rems = get<2>(vec[i]);
while (true) {
col[rems] = cnts; cnt[cnts]++;
ey++;
rems = Map[make_pair(ex, ey)] - 1;
if (rems == -1) break;
}
}
for (int i = 0; i < N; i++) {
int dx[4] = { 1, -1 }, dy[4] = { 0, 0 };
for (int j = 0; j < 2; j++) {
int ex = X[i] + dx[j], ey = Y[i] + dy[j];
int D = Map[make_pair(ex, ey)]; if (D == 0) continue;
int t1 = i, t2 = D - 1;
t1 = col[t1]; t2 = col[t2];
G[t1].push_back(t2);
G[t2].push_back(t1);
}
}
dfs1(1, 0);
for (int i = 1; i <= cnts; i++) used[i] = false;
dfs2(1);
return ans;
}
int DistanceSum(int NN, int *AX, int *AY) {
N = NN; long long finalans = 0;
for (int i = 0; i < N; i++) { X[i] = AX[i]; Y[i] = AY[i]; }
for (int i = 0; i < 2; i++) {
long long ret = solve();
finalans += ret;
for (int j = 0; j < N; j++) swap(X[j], Y[j]);
}
return (finalans / 2LL) % mod;
}
Compilation message
city.cpp: In function 'void dfs1(int, long long int)':
city.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
city.cpp: In function 'void dfs2(int)':
city.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
city.cpp: In function 'long long int solve()':
city.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) {
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2688 KB |
Output is correct |
2 |
Correct |
4 ms |
2688 KB |
Output is correct |
3 |
Correct |
4 ms |
2688 KB |
Output is correct |
4 |
Correct |
4 ms |
2688 KB |
Output is correct |
5 |
Correct |
4 ms |
2688 KB |
Output is correct |
6 |
Correct |
4 ms |
2816 KB |
Output is correct |
7 |
Correct |
4 ms |
2816 KB |
Output is correct |
8 |
Correct |
4 ms |
2688 KB |
Output is correct |
9 |
Correct |
4 ms |
2816 KB |
Output is correct |
10 |
Correct |
5 ms |
2816 KB |
Output is correct |
11 |
Correct |
5 ms |
2816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2944 KB |
Output is correct |
2 |
Correct |
5 ms |
2816 KB |
Output is correct |
3 |
Correct |
6 ms |
2944 KB |
Output is correct |
4 |
Correct |
6 ms |
2944 KB |
Output is correct |
5 |
Correct |
9 ms |
3072 KB |
Output is correct |
6 |
Correct |
7 ms |
3072 KB |
Output is correct |
7 |
Correct |
8 ms |
3072 KB |
Output is correct |
8 |
Correct |
7 ms |
3072 KB |
Output is correct |
9 |
Correct |
7 ms |
3072 KB |
Output is correct |
10 |
Correct |
7 ms |
3072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
5932 KB |
Output is correct |
2 |
Correct |
52 ms |
6336 KB |
Output is correct |
3 |
Correct |
156 ms |
10668 KB |
Output is correct |
4 |
Correct |
154 ms |
11068 KB |
Output is correct |
5 |
Correct |
442 ms |
19092 KB |
Output is correct |
6 |
Correct |
432 ms |
19984 KB |
Output is correct |
7 |
Correct |
462 ms |
19304 KB |
Output is correct |
8 |
Correct |
445 ms |
17980 KB |
Output is correct |
9 |
Correct |
440 ms |
19244 KB |
Output is correct |
10 |
Correct |
498 ms |
24244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
6716 KB |
Output is correct |
2 |
Correct |
59 ms |
6472 KB |
Output is correct |
3 |
Correct |
255 ms |
13060 KB |
Output is correct |
4 |
Correct |
239 ms |
12124 KB |
Output is correct |
5 |
Correct |
760 ms |
23012 KB |
Output is correct |
6 |
Correct |
676 ms |
20296 KB |
Output is correct |
7 |
Correct |
766 ms |
23312 KB |
Output is correct |
8 |
Correct |
607 ms |
21136 KB |
Output is correct |
9 |
Correct |
586 ms |
20772 KB |
Output is correct |
10 |
Correct |
605 ms |
20600 KB |
Output is correct |