///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define mod 1000000000
#define MAXN 100001
ll ans[MAXN];
ll cnt[MAXN];
ll dist[MAXN];
int vis[MAXN];
map<pii,ll> ccnt;
map<pii,ll> cdist;
vector<int> a[MAXN];
vector<int> par[MAXN];
int lca(int x){
int v,u,p,q,r,s;
v=par[x][0];
u=par[x][1];
p=par[v][0];
q=par[v].back();
r=par[u][0];
s=par[u].back();
if(p==r || p==s)
return p;
if(q==r || q==s)
return q;
return 0;
}
void compute(int v){
ll o,p,q,r,s;
cnt[v]+=1;
vector<int> vec;
for(auto& i:a[v]){
if(i!=par[v][0] &&
i!=par[v].back())
vec.append(i);
}
for(auto& i:vec){
cnt[v]+=cnt[i];
dist[v]=(dist[v]+dist[i]+cnt[i])%mod;
}
ans[v]+=dist[v];
for(int i=0;i<vec.size();i++){
for(int j=i+1;j<vec.size();j++){
r=vec[i];
s=vec[j];
p=((cnt[r]-ccnt[{r,s}])*(dist[s]+cnt[s]-cdist[{r,s}]-ccnt[{r,s}]))%mod;
q=((cnt[s]-ccnt[{r,s}])*(dist[r]+cnt[r]-cdist[{r,s}]-ccnt[{r,s}]))%mod;
ans[v]=(ans[v]+p+q)%mod;
}
}
//cout<<v<<' '<<cnt[v]<<' '<<dist[v]<<' '<<ans[v]<<nl;
if(par[v].size()>1){
o=lca(v);
p=par[v][0];
q=par[v][1];
ccnt[{p,q}]=cnt[v];
ccnt[{q,p}]=cnt[v];
cdist[{p,q}]=dist[v]+cnt[v];
cdist[{p,q}]=dist[v]+cnt[v];
cnt[o]-=cnt[v];
dist[o]-=dist[v]+2*cnt[v];
dist[o]=((dist[o]%mod)+mod)%mod;
}
}
void bfs(){
vis[1]=1;
par[1].append(0);
vector<int> u,v{1};
vector<vector<int>> vec;
while(!v.empty()){
vec.append(v);
for(auto& j:v){
for(auto& i:a[j]){
if(i!=par[j][0] &&
i!=par[j].back())
par[i].append(j);
if(!vis[i])
u.append(i);
vis[i]=1;
}
}
swap(v,u);
u.clear();
}
reverse(all(vec));
for(auto& i:vec)
for(auto& j:i)
compute(j);
}
int DistanceSum(int n,int x[MAXN],int y[MAXN]){
map<pii,int> z;
for(int i=0;i<n;i++){
z[{x[i],y[i]}]=i+1;
if(z[{x[i],y[i]-1}]){
a[z[{x[i],y[i]-1}]].append(i+1);
a[i+1].append(z[{x[i],y[i]-1}]);
}
if(z[{x[i],y[i]+1}]){
a[z[{x[i],y[i]+1}]].append(i+1);
a[i+1].append(z[{x[i],y[i]+1}]);
}
if(z[{x[i]-1,y[i]}]){
a[z[{x[i]-1,y[i]}]].append(i+1);
a[i+1].append(z[{x[i]-1,y[i]}]);
}
if(z[{x[i]+1,y[i]}]){
a[z[{x[i]+1,y[i]}]].append(i+1);
a[i+1].append(z[{x[i]+1,y[i]}]);
}
}
bfs();
ll o=0;
for(int i=1;i<=n;i++)
o=(o+ans[i])%mod;
return o;
}
Compilation message
city.cpp: In function 'void compute(int)':
city.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i=0;i<vec.size();i++){
| ~^~~~~~~~~~~
city.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int j=i+1;j<vec.size();j++){
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
77 ms |
13836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
63 ms |
12332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
