oj.uz

Submission #116244

# Submission time Handle Problem Language Result Execution time Memory
116244 2019-06-11T13:39:30 Z nvmdava Ideal city (IOI12_city) C++17
0 / 100
 25 ms 7296 KB 
#include <bits/stdc++.h>
using namespace std;

long long res = 0;

set<pair<int, int> > loc[2];
int t[2], re[2], st, n;
long long sz[2][100005];
vector<int> adj[2][100005];

int dfs(int x, int y){
   int id = ++re[st], q = y++;
   set<pair<int, int> >::iterator it;
   while((it = loc[st].find({x, ++q})) != loc[st].end())
      loc[st].erase(it), sz[st][id]++;

   while((it = loc[st].find({x, --y})) != loc[st].end())
      loc[st].erase(it), sz[st][id]++;

   for(y++; y < q; y++){
      for(int j = -1; j <= 1; j += 2){
         if(loc[st].count({x + 1, y})){
            int w = dfs(x + 1, y);
            adj[st][id].push_back(w);
            sz[st][id] += sz[st][w];
         }
      }

   }
   res += (n - sz[st][id]) * sz[st][id];
   return id;
}

int DistanceSum(int N, int *X, int *Y) {
   n = N;
   for(int i = 0; i < N; i++){
      X[i] -= 9;
      Y[i] -= 9;
      loc[0].insert({X[i], Y[i]});
      loc[1].insert({Y[i], X[i]});
   }
   t[0] = X[0];
   t[1] = Y[0];
   dfs(t[0], t[1]);
   st ^= 1;
   dfs(t[1], t[0]);
   return res % 1000000000;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 7160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 7296 KB Output isn't correct
2 Halted 0 ms 0 KB -