oj.uz

Submission #316034

# Submission time Handle Problem Language Result Execution time Memory
316034 2020-10-24T21:46:10 Z VROOM_VARUN Ideal city (IOI12_city) C++14
100 / 100
 219 ms 28264 KB 
/*
ID: varunra2
LANG: C++
TASK: city
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000000
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

// int calc(int *x, int n) {
//   ll ret = 0;
//   ll sum = 0;
//   for(ll i = 0; i < n; i++) {
//     ret += abs(x[i] * i - sum);
//     sum += x[i];
//     ret %= INF;
//     sum %= INF;
//   }
//   return ret;
// }

struct dsu {
  VI par;
  VI siz;
  int n;
  void init(int _n) {
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    siz.assign(n, 1);
  }
  int find(int x) {
    while (par[x] != par[par[x]]) par[x] = par[par[x]];
    return par[x];
  }
  bool isPar(int x) { return x == find(x); }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (siz[x] < siz[y]) swap(x, y);
    par[y] = x;
    siz[x] += siz[y];
    return true;
  }
  void pr() {
    debug("printing tree's dsu");
    debug(siz);
  }
};

struct tree {
  int n;
  VVI adj;
  dsu ds;
  vector<ll> sub;
  vector<ll> ret;
  int tot;

  void init(int _n) {
    n = _n;
    adj.resize(n);
    ds.init(n);
    ret.resize(n);
    sub.resize(n);
  }

  void addEdge(int u, int v) {
    adj[u].PB(v);
    adj[v].PB(u);
  }

  void cleanAdj() {
    trav(x, adj) {
      sort(all(x));
      x.resize(unique(all(x)) - x.begin());
    }
  }

  void genAdj(VI& a, VI& b) {
    VII vals(n);
    for (int i = 0; i < n; i++) {
      vals[i] = MP(a[i], b[i]);
    }
    sort(all(vals));
    for (int i = 0; i < n - 1; i++) {
      if (vals[i].x == vals[i + 1].x and vals[i].y == vals[i + 1].y - 1) {
        ds.merge(i, i + 1);
      }
    }
    map<PII, int> mp;
    for (int i = 0; i < n; i++) {
      mp[vals[i]] = ds.find(i) + 1;
    }
    for (int i = 0; i < n; i++) {
      int u = ds.find(i);
      int ind;
      ind = mp[MP(vals[i].x - 1, vals[i].y)];
      if (ind) {
        addEdge(u, ind - 1);
      }
      ind = mp[MP(vals[i].x + 1, vals[i].y)];
      if (ind) {
        addEdge(u, ind - 1);
      }
    }
    cleanAdj();
    tot = 0;
    for (int i = 0; i < n; i++) {
      if (i == ds.find(i)) tot++;
    }
  }

  void dfs(int u, int v) {
    sub[u] = ds.siz[u];
    for (auto& x : adj[u]) {
      if (x == v) continue;
      dfs(x, u);
      sub[u] += sub[x];
      ret[u] += sub[x] * (1ll * n - sub[x]);
    }
    return;
  }

  int calc() {
    dfs(0, -1);
    return (accumulate(all(ret), 0ll) % INF);
  }
  void pr() {
    debug("printing tree");
    debug(adj);
    debug(ret);
    debug(sub);
    ds.pr();
  }
};

int DistanceSum(int n, int* x, int* y) {
  VI a(n);
  VI b(n);
  for (int i = 0; i < n; i++) {
    a[i] = x[i];
    b[i] = y[i];
  }
  tree hor, ver;
  hor.init(n);
  ver.init(n);
  hor.genAdj(a, b);
  ver.genAdj(b, a);
  int v1, v2;
  v1 = hor.calc();
  v2 = ver.calc();
  // debug(v1, v2);
  hor.pr();
  ver.pr();
  int ret = (v1 + v2) % MOD;
  return ret;
}

// int main() {
// #ifndef ONLINE_JUDGE
//   freopen("city.in", "r", stdin);
//   freopen("city.out", "w", stdout);
// #endif
//   cin.sync_with_stdio(0);
//   cin.tie(0);

//   int n;
//   cin >> n;

//   int x[n];
//   int y[n];

//   for (int i = 0; i < n; i++) {
//     cin >> x[i] >> y[i];
//   }

//   cout << DistanceSum(n, x, y) << '\n';

//   return 0;
// }

Compilation message

city.cpp: In member function 'void dsu::pr()':
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:92:5: note: in expansion of macro 'debug'
   92 |     debug("printing tree's dsu");
      |     ^~~~~
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:93:5: note: in expansion of macro 'debug'
   93 |     debug(siz);
      |     ^~~~~
city.cpp: In member function 'void tree::pr()':
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:175:5: note: in expansion of macro 'debug'
  175 |     debug("printing tree");
      |     ^~~~~
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:176:5: note: in expansion of macro 'debug'
  176 |     debug(adj);
      |     ^~~~~
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:177:5: note: in expansion of macro 'debug'
  177 |     debug(ret);
      |     ^~~~~
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:178:5: note: in expansion of macro 'debug'
  178 |     debug(sub);
      |     ^~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 3 ms 672 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 4 ms 896 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 768 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4952 KB Output is correct
2 Correct 31 ms 5124 KB Output is correct
3 Correct 82 ms 12012 KB Output is correct
4 Correct 81 ms 11888 KB Output is correct
5 Correct 170 ms 24228 KB Output is correct
6 Correct 169 ms 23656 KB Output is correct
7 Correct 175 ms 23936 KB Output is correct
8 Correct 168 ms 24276 KB Output is correct
9 Correct 168 ms 23012 KB Output is correct
10 Correct 180 ms 28264 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5592 KB Output is correct
2 Correct 37 ms 5592 KB Output is correct
3 Correct 103 ms 13680 KB Output is correct
4 Correct 98 ms 13168 KB Output is correct
5 Correct 219 ms 27136 KB Output is correct
6 Correct 199 ms 25320 KB Output is correct
7 Correct 217 ms 27240 KB Output is correct
8 Correct 208 ms 25188 KB Output is correct
9 Correct 194 ms 24680 KB Output is correct
10 Correct 192 ms 24676 KB Output is correct