| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1024394 |
2024-07-16T03:47:18 Z |
socpite |
Ideal city (IOI12_city) |
C++17 |
|
133 ms |
23136 KB |
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int mod = 1e9;
vector<int> g[maxn];
int W[maxn];
long long dfs(int x, int p, int N){
long long re = 0;
for(auto v: g[x]){
if(v == p)continue;
re += dfs(v, x, N);
W[x] += W[v];
}
re += 1LL*W[x]*(N - W[x])%mod;
re %= mod;
return re;
}
long long solve(int N, int *X, int *Y){
for(int i = 1; i <= N; i++){
g[i].clear();
W[i] = 0;
}
int cnt = 0;
map<int, set<int>> mp;
map<pair<int, int>, int> id;
for(int i = 0; i < N; i++)mp[X[i]].insert(Y[i]);
for(auto v: mp){
int prv = -2;
for(auto pos: v.second){
if(pos == prv + 1)id[{v.first, pos}] = cnt;
else id[{v.first, pos}] = ++cnt;
W[cnt]++;
if(id.find({v.first-1, pos}) != id.end()){
int prvid = id[{v.first-1, pos}];
g[cnt].push_back(prvid);
g[prvid].push_back(cnt);
}
prv = pos;
}
}
for(int i = 1; i <= cnt; i++){
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
}
return dfs(1, 0, N);
}
int DistanceSum(int N, int *X, int *Y) {
long long ans = solve(N, X, Y);
for(int i = 0; i < N; i++)swap(X[i], Y[i]);
ans += solve(N, X, Y);
return ans%mod;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
1 ms |
3016 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3044 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3164 KB |
Output is correct |
| 7 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 9 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
21 ms |
6236 KB |
Output is correct |
| 3 |
Correct |
54 ms |
10064 KB |
Output is correct |
| 4 |
Correct |
54 ms |
10660 KB |
Output is correct |
| 5 |
Correct |
111 ms |
17140 KB |
Output is correct |
| 6 |
Correct |
116 ms |
18216 KB |
Output is correct |
| 7 |
Correct |
115 ms |
17940 KB |
Output is correct |
| 8 |
Correct |
113 ms |
17068 KB |
Output is correct |
| 9 |
Correct |
116 ms |
18004 KB |
Output is correct |
| 10 |
Correct |
124 ms |
23136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
5980 KB |
Output is correct |
| 2 |
Correct |
26 ms |
6192 KB |
Output is correct |
| 3 |
Correct |
61 ms |
10320 KB |
Output is correct |
| 4 |
Correct |
59 ms |
10556 KB |
Output is correct |
| 5 |
Correct |
130 ms |
17696 KB |
Output is correct |
| 6 |
Correct |
133 ms |
18004 KB |
Output is correct |
| 7 |
Correct |
124 ms |
17748 KB |
Output is correct |
| 8 |
Correct |
127 ms |
17656 KB |
Output is correct |
| 9 |
Correct |
119 ms |
17376 KB |
Output is correct |
| 10 |
Correct |
119 ms |
17492 KB |
Output is correct |
