This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma once
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const int mxN = 2e5 + 5;
const int mod = 1e9;
using namespace std;
vector<vector<int>>v;
ll dpD[mxN],dpU[mxN];
ll subD[mxN],subU[mxN];
ll w[mxN];
int p[mxN];
ll ans;
int _N;
void dfs(int u,int par){
subD[u] = w[u];
p[u] = par;
for(auto x : v[u]){
if(x == par) continue;
dfs(x,u);
subD[u] += subD[x];
}
dpD[u] = (long long) subD[u] * (_N - subD[u]);
}
ll solve(int N,int X[],int Y[]){
ans = 0;
for(int i = 0; i <= N;i++){
dpD[i] = 0;
dpU[i] = 0;
subD[i] = 0;
subU[i] = 0;
w[i] = 0;
p[i] = 0;
}
map<pii,int>mp;
map<pii,bool>vis;
for(auto &x : v) x.clear();
v.clear();
v.resize(N + 1);
int id = 0;
vector<pii>a;
for(int i = 0;i < N;i++){
a.push_back({X[i],Y[i]});
}
sort(a.begin(),a.end());
int pX = -1,pY = -1;
for(auto x : a){
if(x.F != pX || x.S != pY + 1){
id++;
}
mp[x] = id;
w[id]++;
if(mp[{x.F - 1,x.S}] && !vis[{mp[x],mp[{x.F - 1,x.S}]}]){
v[mp[{x.F - 1,x.S}]].push_back(mp[x]);
v[mp[x]].push_back(mp[{x.F - 1,x.S}]);
vis[{mp[x],mp[{x.F - 1,x.S}]}] = 1;
}
pX = x.F;
pY = x.S;
}
// for(int i = 1;i < 7;i++){
// cout<<i<<' '<<w[i]<<"{ ";
// for(auto x : v[i]){
// cout<<x<<' ';
// }
// cout<<"}\n";
// }
dfs(1,0);
for(int i = 1;i <= N;i++){
ans += dpD[i] ;
// cout<<dpD[i]<<' ';
}
// cout<<'\n';
// for(int i = 1;i <= N;i++){
// cout<<dpU[i]<<' ';
// }
// cout<<'\n';
// cout<<'\n';
// ans /= 2;
// ans %= mod;
return ans;
}
int DistanceSum(int N, int X[], int Y[]){
_N = N;
return (((solve(N,Y,X) + solve(N,X,Y))) % mod);
}
Compilation message (stderr)
city.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |