Submission #987793

#	Time	Username	Problem	Language	Result	Execution time	Memory
987793		huutuan	Ideal city (IOI12_city)	C++14	100 / 100	59 ms	8540 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45