Submission #56220

#	Time	Username	Problem	Language	Result	Execution time	Memory
56220		ruhanhabib39	Ideal city (IOI12_city)	C++17	100 / 100	559 ms	53156 KiB

city

#include <bits/stdc++.h>

namespace {
   using namespace std;
   
   const int MAXN = 1e5;
   const long long MOD = 1e9;

   int N, *X, *Y;
   vector<int> atX[MAXN + 10], atY[MAXN + 10];
   vector<pair<int,int>> G[MAXN + 10];
   set<tuple<int,int,int>> st;
   map<int,int> val, mp;
   map<int,map<int,int>> id;
   int par[MAXN + 10];

   long long cc[MAXN + 10], dis[MAXN + 10], sum[MAXN + 10];

   void dfs(int u, int p = -1) {
      for(auto e : G[u]) {
         int v, w; tie(v, w) = e;
         if(v != p) dfs(v, u);
      }
      cc[u] = 1; dis[u] =  0;
      for(auto e : G[u]) {
         int v, w; tie(v, w) = e;
         if(v == p) continue;
         cc[u] += cc[v];
         dis[u] += w*cc[v] + dis[v];
      }
      sum[u] = 0;
      for(auto e : G[u]) {
         int v, w; tie(v, w) = e;
         if(v == p) continue;
         sum[u] += sum[v];
         sum[u] += (dis[v] + w*cc[v]) * (cc[u] - cc[v]);
      }
   }

   long long calc(vector<int> at[MAXN + 10]) {
      fill(G, G + MAXN + 1, vector<pair<int,int>>());
      st.clear(); id.clear();
      memset(par, -1, sizeof par);

      int jj = 0;
      for(int x = 1; x <= N; x++) {
         for(int y : at[x]) id[x][y] = ++jj;
      }

      set<pair<int,int>> yay;
      jj = 0;
      for(int x = 1; x <= N; x++) {
         int l = 0, r = 0;
         while(l < (int)at[x].size()) {
            r = l;
            while(r+1 < (int)at[x].size() && at[x][r+1] == at[x][r]+1) {
               r++;
            }
            ++jj;
            for(int i = l; i <= r; i++) {
               par[id[x][at[x][i]]] = jj;
            }
            //cerr << "[" << val[at[x][l]] << ", " << val[at[x][r]] << "]\n";
            for(int i = l; i <= r; i++) {
               auto add = [&](int a, int b, int c, int d, int w) {
                  int u = id[a][b], v = id[c][d];
                  st.emplace(u, v, w);
                  st.emplace(v, u, w);
                  yay.emplace(par[u], par[v]);
                  yay.emplace(par[v], par[u]);
               };
               int y = at[x][i];
               if(i < r) add(x, y, x, y+1, 0);
               if(binary_search(at[x-1].begin(), at[x-1].end(), y)) {
                  if(!yay.count({par[id[x][y]], par[id[x-1][y]]})) {
                     //cerr << "yay " << val[x] << " " << val[y] << " " << val[x-1] << " " << val[y] << "\n";
                     add(x, y, x-1, y, 1);
                  } else {
                     //cerr << "bad " << val[x] << " " << val[y] << " " << val[x-1] << " " << val[y] << "\n";
                  }
               }

            }
            l = r+1;
         }
      }

      for(auto it : st) {
         int u, v, w; tie(u, v, w) = it;
         G[u].emplace_back(v, w);
      }

      dfs(1);

      return sum[1];
   }
};

int DistanceSum(int N_, int* X_, int* Y_) {
   N = N_; X = X_; Y = Y_;
   set<int> st;
   for(int i = 0; i < N; i++) {
      st.insert(X[i]);
      st.insert(Y[i]);
   }
   int ii = 0;
   for(int x : st) {
      mp[x] = ++ii;
      val[ii] = x;
   }

   for(int i = 0; i < N; i++) {
      X[i] = mp[X[i]];
      Y[i] = mp[Y[i]];
   }

   for(int i = 0; i < N; i++) {
      atX[X[i]].push_back(Y[i]);
      atY[Y[i]].push_back(X[i]);
   }
   for(int x = 1; x <= N; x++) {
      sort(atX[x].begin(), atX[x].end());
   }
   for(int y = 1; y <= N; y++) {
      sort(atY[y].begin(), atY[y].end());
   }

   long long res = calc(atX);
   //cerr << "\n\n\n";
   res += calc(atY);
   return res % MOD;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45