oj.uz

Submission #522090

# Submission time Handle Problem Language Result Execution time Memory
522090 2022-02-03T19:59:34 Z cadmiumsky Ideal city (IOI12_city) C++14
32 / 100
 32 ms 2872 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
//g++ -std=c++17 -Wshadow -Wall -Wextra -o "%e" "%f" -g -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG
int n;
int nodes;

static ll solve(int *X, int *Y) {
  nodes = 0;
  map<int, set<int> > mat;
  map<int,int> w;
  map<int, map<int, int> > col;
  for(int i = 0; i < n; i++)
    col[X[i]][Y[i]];
  set<pair<int, int> > edg;
  vector<vector<int> > g;
  for(auto &v : col) {
    int x = v.first;
    for(auto &y : v.second) {
      if(col[x].find(y.first - 1) != col[x].end())
        y.second = col[x][y.first - 1], w[y.second]++;
      else
        w[nodes] = 1, y.second = nodes++;
      if(col.find(x - 1) == col.end() || col[x - 1].find(y.first) == col[x - 1].end()) 
        continue;
      //cerr << y.second<< ' '  <<  x << ' ' << y.first << ' ' << col[x - 1][y.first] << '\n';
      edg.insert({col[x - 1][y.first], col[x][y.first]});
    }
  }
  g.resize(nodes);
  for(auto x : edg) {
    //cerr << x.first << ' ' << x.second << '\n';
    g[x.first].push_back(x.second);
    g[x.second].push_back(x.first);
  }
  //cerr << "Ma-ta\n";
  ll total = 0;
  function<ll(int,int)> dfs = [&](int node, int f) {
    int sum = w[node];
    for(auto x : g[node])
      if(x != f)
        sum += dfs(x, node);
    //cerr << node << ' ' << f << ' ' << w[node] << '\n';
    total += (ll)(n - sum) * sum;
    return sum;
  };
  dfs(0, 0);
  return total;
}
int DistanceSum(int N, int *X, int *Y) {
  n = N;
  return solve(X, Y) + solve(Y, X);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 3 ms 428 KB Output is correct
10 Correct 4 ms 420 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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