oj.uz

Submission #56220

# Submission time Handle Problem Language Result Execution time Memory
56220 2018-07-10T09:26:18 Z ruhanhabib39 Ideal city (IOI12_city) C++17
100 / 100
 559 ms 53156 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7800 KB Output is correct
2 Correct 11 ms 7912 KB Output is correct
3 Correct 14 ms 7912 KB Output is correct
4 Correct 11 ms 7948 KB Output is correct
5 Correct 13 ms 7952 KB Output is correct
6 Correct 11 ms 7956 KB Output is correct
7 Correct 11 ms 7956 KB Output is correct
8 Correct 14 ms 7968 KB Output is correct
9 Correct 13 ms 8100 KB Output is correct
10 Correct 12 ms 8100 KB Output is correct
11 Correct 10 ms 8100 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8412 KB Output is correct
2 Correct 12 ms 8412 KB Output is correct
3 Correct 19 ms 8744 KB Output is correct
4 Correct 18 ms 8744 KB Output is correct
5 Correct 20 ms 9020 KB Output is correct
6 Correct 18 ms 9020 KB Output is correct
7 Correct 15 ms 9020 KB Output is correct
8 Correct 15 ms 9020 KB Output is correct
9 Correct 17 ms 9020 KB Output is correct
10 Correct 15 ms 9020 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 13676 KB Output is correct
2 Correct 85 ms 13964 KB Output is correct
3 Correct 167 ms 21592 KB Output is correct
4 Correct 205 ms 22288 KB Output is correct
5 Correct 419 ms 35464 KB Output is correct
6 Correct 384 ms 36536 KB Output is correct
7 Correct 382 ms 37492 KB Output is correct
8 Correct 353 ms 37492 KB Output is correct
9 Correct 370 ms 39092 KB Output is correct
10 Correct 515 ms 53156 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 53156 KB Output is correct
2 Correct 92 ms 53156 KB Output is correct
3 Correct 206 ms 53156 KB Output is correct
4 Correct 267 ms 53156 KB Output is correct
5 Correct 559 ms 53156 KB Output is correct
6 Correct 536 ms 53156 KB Output is correct
7 Correct 470 ms 53156 KB Output is correct
8 Correct 555 ms 53156 KB Output is correct
9 Correct 407 ms 53156 KB Output is correct
10 Correct 427 ms 53156 KB Output is correct