oj.uz

Submission #116242

# Submission time Handle Problem Language Result Execution time Memory
116242 2019-06-11T13:32:47 Z nvmdava Ideal city (IOI12_city) C++17
55 / 100
 285 ms 32632 KB 
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000000

long long res = 0;

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

int dfs(int x, int y){
   int id = ++re[1];
   int 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++){
      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];
      }
      if(loc[st].count({x - 1, y})){
         int w = dfs(x - 1, y);
         sz[st][id] += sz[st][w];
         adj[st][id].push_back(dfs(x - 1, y));
      }
   }
   res += 1LL * (n - sz[st][id]) * sz[st][id];
   return id;
}

void solve(){
   dfs(t[st], t[st ^ 1]);
   st ^= 1;
}

int DistanceSum(int N, int *X, int *Y) {
   n = N;
   for(int i = 0; i < N; i++){
      X[i] -= 26543;
      Y[i] -= 51844;
      loc[0].insert({X[i], Y[i]});
      loc[1].insert({Y[i], X[i]});
   }
   t[0] = X[0];
   t[1] = Y[0];
   solve();
   solve();

   return res % MOD;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 7 ms 5092 KB Output is correct
10 Correct 6 ms 5120 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 9 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 9 ms 5248 KB Output is correct
5 Correct 9 ms 5248 KB Output is correct
6 Correct 9 ms 5248 KB Output is correct
7 Correct 9 ms 5376 KB Output is correct
8 Correct 9 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 9 ms 5248 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7288 KB Output is correct
2 Correct 26 ms 7288 KB Output is correct
3 Correct 69 ms 10616 KB Output is correct
4 Correct 67 ms 10588 KB Output is correct
5 Correct 160 ms 16248 KB Output is correct
6 Correct 158 ms 16112 KB Output is correct
7 Correct 200 ms 16492 KB Output is correct
8 Correct 170 ms 16000 KB Output is correct
9 Correct 214 ms 16372 KB Output is correct
10 Correct 223 ms 19192 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7512 KB Output is correct
2 Correct 39 ms 7544 KB Output is correct
3 Correct 119 ms 11128 KB Output is correct
4 Correct 100 ms 11000 KB Output is correct
5 Runtime error 285 ms 32632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -