oj.uz

Submission #116245

# Submission time Handle Problem Language Result Execution time Memory
116245 2019-06-11T13:40:02 Z nvmdava Ideal city (IOI12_city) C++17
100 / 100
 282 ms 17968 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 + j, y})){
            int w = dfs(x + j, 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
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7168 KB Output is correct
2 Correct 27 ms 7168 KB Output is correct
3 Correct 64 ms 10236 KB Output is correct
4 Correct 65 ms 10360 KB Output is correct
5 Correct 179 ms 15352 KB Output is correct
6 Correct 167 ms 15532 KB Output is correct
7 Correct 174 ms 15608 KB Output is correct
8 Correct 187 ms 15400 KB Output is correct
9 Correct 224 ms 15632 KB Output is correct
10 Correct 224 ms 17968 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7308 KB Output is correct
2 Correct 35 ms 7296 KB Output is correct
3 Correct 122 ms 10824 KB Output is correct
4 Correct 95 ms 10588 KB Output is correct
5 Correct 266 ms 16200 KB Output is correct
6 Correct 267 ms 15848 KB Output is correct
7 Correct 282 ms 16352 KB Output is correct
8 Correct 257 ms 15948 KB Output is correct
9 Correct 238 ms 15728 KB Output is correct
10 Correct 201 ms 15608 KB Output is correct