oj.uz

Submission #987793

# Submission time Handle Problem Language Result Execution time Memory
987793 2024-05-23T15:28:40 Z huutuan Ideal city (IOI12_city) C++14
100 / 100
 59 ms 8540 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e5+10, mod=1e9;
int n, m, cnt[N], sz[N], ans;
pair<int, int> a[N];
vector<int> g[N];

void dfs_sz(int u, int p){
   sz[u]=cnt[u];
   for (int v:g[u]) if (v!=p) dfs_sz(v, u), sz[u]+=sz[v];
}

void dfs(int u, int p){
   for (int v:g[u]) if (v!=p){
      dfs(v, u);
      ans=(ans+sz[v]*(n-sz[v]))%mod;
   }
}

void solve(){
   m=0;
   sort(a+1, a+n+1);
   vector<pair<int, int>> v1, v2;
   for (int i=1; i<=n; ++i){
      int j=i;
      while (j<n && a[i].first==a[j+1].first && a[j].second+1==a[j+1].second) ++j;
      ++m;
      cnt[m]=j-i+1;
      v2.emplace_back(a[i].second, a[j].second);
      if (j==n || a[i].first!=a[j+1].first){
         for (int i2=0, i1=0; i2<(int)v2.size(); ++i2){
            while (i1<(int)v1.size() && v1[i1].first<=v2[i2].second) ++i1;
            int it=i1-1;
            while (it>=0 && max(v1[it].first, v2[i2].first)<=min(v1[it].second, v2[i2].second)){
               g[m-(int)v2.size()-(int)v1.size()+it+1].push_back(m-(int)v2.size()+i2+1);
               g[m-(int)v2.size()+i2+1].push_back(m-(int)v2.size()-(int)v1.size()+it+1);
               --it;
            }
         }
         v1=v2;
         v2.clear();
      }
      i=j;
   }
   dfs_sz(1, 0);
   dfs(1, 0);
   for (int i=1; i<=m; ++i){
      g[i].clear();
      cnt[i]=sz[i]=0;
   }
}

int32_t DistanceSum(int32_t _N, int32_t *X, int32_t *Y) {
   n=_N;
   for (int i=1; i<=n; ++i) a[i]={X[i-1], Y[i-1]};
   solve();
   for (int i=1; i<=n; ++i) a[i]={Y[i-1], X[i-1]};
   solve();
   return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4920 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 2 ms 4708 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4956 KB Output is correct
2 Correct 8 ms 4956 KB Output is correct
3 Correct 16 ms 5032 KB Output is correct
4 Correct 16 ms 5212 KB Output is correct
5 Correct 31 ms 5468 KB Output is correct
6 Correct 31 ms 5724 KB Output is correct
7 Correct 34 ms 5564 KB Output is correct
8 Correct 36 ms 5500 KB Output is correct
9 Correct 33 ms 5720 KB Output is correct
10 Correct 35 ms 8540 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5212 KB Output is correct
2 Correct 8 ms 5080 KB Output is correct
3 Correct 21 ms 6140 KB Output is correct
4 Correct 19 ms 5724 KB Output is correct
5 Correct 59 ms 7504 KB Output is correct
6 Correct 42 ms 6484 KB Output is correct
7 Correct 43 ms 7504 KB Output is correct
8 Correct 39 ms 6480 KB Output is correct
9 Correct 39 ms 6096 KB Output is correct
10 Correct 36 ms 6084 KB Output is correct