#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
template <class T>
void rd(T &x) {
int sgn = 1;
char ch;
x = 0;
for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
if (ch == '-') ch = getchar(), sgn = -1;
for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
x *= sgn;
}
template <class T>
void wr(T x) {
if (x < 0) putchar('-'), wr(-x);
else if (x < 10) putchar(x + '0');
else wr(x / 10), putchar(x % 10 + '0');
}
void usaco(string s){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
/*
think of it as a tree
we dont need to acc for each node
we keep track of hor and ver
for children of node
we add child dist + (sum of alldist without that child)
dist can be split as hor and ver can be handled separately
but how to implement
because dist remains const
we use that fact
how to maintain cleanly
each node can go hor or ver
if both hor ver or other sides then treat each as subtree
for each node we keep count of vals coming to it
so we can add those to our subtree
dist trav hor dist trav ver is the parent stuff
but at each node we need to add 1 + 2 + 3 - - - n
n(n+1)/2 added each time?
no
at each level theres certain number of nodes
so we need to somehow take that into account
when we go down ver
we have to add it num of times we visited it horizontally
when we go down more we just add hor to it that will take in account the going down
by 1 vertically
work backwards?
hor tree ver tree
*/
const int maxn = 1e5 + 5, MOD = 1e9;;
vector<pair<int, int>> a;
ll ans = 0, n;
int tls[maxn], csize[maxn];
multiset<int> adj[maxn];
vector<bool> vis(maxn, 0);
void dfs(int u){
vis[u] = 1;
//cerr << u << '\n';
for(auto c : adj[u]){
if(!vis[c]){
dfs(c);
csize[u] += csize[c];
}
}
ans = (ans + (1ll * csize[u] * (n - csize[u])) % MOD) % MOD;
}
void solve(){
int i = 0, m = 0;
sort(a.begin(),a.end());
rep(i, 0, n){
adj[i].clear();
}
while(i < n){
int j = i + 1; tls[i] = m;
while(j < n and a[j] == make_pair(a[j - 1].first, a[j - 1].second + 1)){
//cerr << j << ' ' << tls[j] << ' ' << m << '\n';
tls[j++] = m;
}
csize[m] = j - i; i = j;
//cerr << i << ' ' << csize[m] << '\n';
m++;
}
cerr << "hello";
int j = 0;
rep(i, 0, n){
for(; j < n and a[j] < make_pair(a[i].first - 1 , a[i].second); j++){cerr<<"hi";}
if(j < n and a[j] == make_pair(a[i].first - 1 , a[i].second)){
//cerr << tls[i] << " -> " << tls[j] << '\n';
adj[tls[i]].insert(tls[j]);
adj[tls[j]].insert(tls[i]);
}
}
rep(i, 0, (int)vis.size()){
vis[i] = 0;
}
dfs(0);
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
rep(i, 0, n){
a.emplace_back(X[i], Y[i]);
}
solve();
rep(i, 0, n){
//easy way to do it is to just rev coord
//a[i].first =
swap(a[i].first,a[i].second);
}
solve();
return ans % MOD;
}
/*
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
freopen("input.txt", "r", stdin);
#endif
}
*/
Compilation message
city.cpp: In function 'void usaco(std::string)':
city.cpp:29:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
29 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
30 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
10 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
11 ms |
5228 KB |
Output is correct |
| 4 |
Correct |
12 ms |
5248 KB |
Output is correct |
| 5 |
Correct |
14 ms |
5228 KB |
Output is correct |
| 6 |
Correct |
14 ms |
5356 KB |
Output is correct |
| 7 |
Correct |
14 ms |
5228 KB |
Output is correct |
| 8 |
Correct |
14 ms |
5228 KB |
Output is correct |
| 9 |
Correct |
14 ms |
5248 KB |
Output is correct |
| 10 |
Correct |
15 ms |
5228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
7400 KB |
Output is correct |
| 2 |
Correct |
113 ms |
7784 KB |
Output is correct |
| 3 |
Correct |
275 ms |
11468 KB |
Output is correct |
| 4 |
Correct |
269 ms |
11436 KB |
Output is correct |
| 5 |
Correct |
564 ms |
17704 KB |
Output is correct |
| 6 |
Correct |
569 ms |
17768 KB |
Output is correct |
| 7 |
Correct |
542 ms |
17828 KB |
Output is correct |
| 8 |
Correct |
562 ms |
17592 KB |
Output is correct |
| 9 |
Correct |
549 ms |
17768 KB |
Output is correct |
| 10 |
Correct |
496 ms |
19816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
6800 KB |
Output is correct |
| 2 |
Correct |
107 ms |
7272 KB |
Output is correct |
| 3 |
Correct |
255 ms |
9708 KB |
Output is correct |
| 4 |
Correct |
264 ms |
10476 KB |
Output is correct |
| 5 |
Correct |
515 ms |
14312 KB |
Output is correct |
| 6 |
Correct |
533 ms |
16616 KB |
Output is correct |
| 7 |
Correct |
517 ms |
14312 KB |
Output is correct |
| 8 |
Correct |
533 ms |
16420 KB |
Output is correct |
| 9 |
Correct |
533 ms |
16668 KB |
Output is correct |
| 10 |
Correct |
541 ms |
16836 KB |
Output is correct |
