oj.uz

Submission #465816

# Submission time Handle Problem Language Result Execution time Memory
465816 2021-08-16T19:12:13 Z alexxela12345 Fountain Parks (IOI21_parks) C++17
5 / 100
 3404 ms 145860 KB 
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rd(179);

int randint(int l, int r) {
  int b = r - l + 1;
  int a = rd() % b + b;
  a %= b;
  return a + l;
}

vector<int> pa, ra;

int get(int v) {
  if (pa[v] == v)
    return v;
  return pa[v] = get(pa[v]);
}
void merge(int a, int b) {
  a = get(a);
  b = get(b);
  assert(a != b);
  if (ra[b] > ra[a])
    swap(a, b);
  pa[b] = a;
  if (ra[a] == ra[b])
    ra[a]++;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
  if (x.size() == 1) {
    build({}, {}, {}, {});
    return 1;
  }
  map<pair<int, int>, int> byc;
  int n = x.size();
  for (int i = 0; i < n; i++) {
    byc[{x[i], y[i]}] = i;
  }
  vector<vector<int>> g(n);
  map<pair<int, int>, int> cnt;
  pa.assign(n, 0);
  ra.assign(n, 0);
  iota(pa.begin(), pa.end(), 0);
  set<pair<int, int>> alive;

  auto add = [&](int i, int j) {
    if (i < j) {
      alive.insert({i, j});
      g[i].push_back(j);
      g[j].push_back(i);
      if (x[i] == x[j]) {
        cnt[{x[i] + 1, (y[i] + y[j]) / 2}] += 1;
        cnt[{x[i] - 1, (y[i] + y[j]) / 2}] += 1;
      } else {
        cnt[{(x[i] + x[j]) / 2, y[i] + 1}] += 1;
        cnt[{(x[i] + x[j]) / 2, y[i] - 1}] += 1;
      }
    }
  };
  for (int i = 0; i < n; i++) {
    {
      pair<int, int> pp = {x[i], y[i]};
      pp.first += 2;
      if (byc.count(pp)) {
        add(i, byc[pp]);
      }
    }
    {
      pair<int, int> pp = {x[i], y[i]};
      pp.second += 2;
      if (byc.count(pp)) {
        add(i, byc[pp]);
      }
    }
    {
      pair<int, int> pp = {x[i], y[i]};
      pp.first -= 2;
      if (byc.count(pp)) {
        add(i, byc[pp]);
      }
    }
    {
      pair<int, int> pp = {x[i], y[i]};
      pp.second -= 2;
      if (byc.count(pp)) {
        add(i, byc[pp]);
      }
    }
  }
  vector<int> used(n);
  function<void(int)> dfs;
  dfs = [&](int v) {
    used[v] = 1;
    for (int u : g[v]) {
      if (!used[u]) {
        dfs(u);
      }
    }
  };
  dfs(0);
  if (*min_element(used.begin(), used.end()) == 0) {
    return 0;
  }
  set<pair<int, int>> ones;
  for (auto &el : cnt) {
    if (el.second == 1) {
      ones.insert(el.first);
    }
  }
  vector<int> u, v, a, b;

  g.clear();
  g.resize(n);

  auto chk = [&](pair<int, int> pp) {
    cnt[pp] -= 1;
    switch (cnt[pp]) {
    case 1: {
      ones.insert(pp);
    };
    case 0: {
      ones.erase(pp);
    };
    }
  };

  auto die = [&](int i, int j) {
    if (j < i)
      swap(i, j);
    alive.erase({i, j});
    if (x[i] == x[j]) {
      pair<int, int> pp;
      pp = {x[i] + 1, (y[i] + y[j]) / 2};
      chk(pp);
      pp = {x[i] - 1, (y[i] + y[j]) / 2};
      chk(pp);
    } else {
      pair<int, int> pp;
      pp = {(x[i] + x[j]) / 2, y[i] + 1};
      chk(pp);
      pp = {(x[i] + x[j]) / 2, y[i] - 1};
      chk(pp);
    }
  };
  auto al = [&](int i, int j) {
    if (j < i)
      swap(i, j);
    return alive.count({i, j});
  };
  auto check_edge = [&](int i, int j, pair<int, int> xy) {
    if (al(i, j) && get(i) != get(j)) {
      u.push_back(i);
      v.push_back(j);
      a.push_back(xy.first);
      b.push_back(xy.second);
      die(i, j);
    } else if (al(i, j)) {
      die(i, j);
    }
  };

  while (true) {
    while (!ones.empty()) {
      pair<int, int> xy = *ones.begin();
      ones.erase(ones.begin());
      pair<int, int> RU, RD, LD, LU;
      RU = RD = LD = LU = xy;
      RU.first++, RU.second++;
      RD.first++, RD.second--;
      LU.first--, LU.second++;
      LD.first--, LD.second--;
      size_t was = u.size();
      if (byc.count(RU) && byc.count(RD)) {
        int i = byc[RU];
        int j = byc[RD];
        check_edge(i, j, xy);
      }
      if (byc.count(RD) && byc.count(LD)) {
        int i = byc[RD];
        int j = byc[LD];
        check_edge(i, j, xy);
      }
      if (byc.count(LD) && byc.count(LU)) {
        int i = byc[LD];
        int j = byc[LU];
        check_edge(i, j, xy);
      }
      if (byc.count(LU) && byc.count(RU)) {
        int i = byc[LU];
        int j = byc[RU];
        check_edge(i, j, xy);
      }
      if (u.size() != was) {
        cnt[xy] = -100;
      }
      assert(u.size() - was <= 1);
    }
    auto alive2 = alive;
    vector<pair<int, int>> kek;
    for (auto [i, j] : alive2) {
      if (get(i) == get(j)) {
        die(i, j);
      } else {
        kek.push_back({i, j});
      }
    }
    if (ones.empty()) {
      if (alive.empty() || clock() > 3 * CLOCKS_PER_SEC)
	break;
      int ind = randint(0, kek.size() - 1);
      auto [i, j] = kek[ind];
      vector<pair<int, int>> can;
      pair<int, int> pp;
      if (x[i] == x[j]) {
	pp = {x[i] + 1, (y[i] + y[j]) / 2};
	if (cnt[pp] >= 0) {
	  can.push_back(pp);
	}
	pp = {x[i] - 1, (y[i] + y[j]) / 2};
	if (cnt[pp] >= 0) {
	  can.push_back(pp);
	}
      } else {
	pp = {(x[i] + x[j]) / 2, y[i] + 1};
	if (cnt[pp] >= 0) {
	  can.push_back(pp);
	}
	pp = {(x[i] + x[j]) / 2, y[i] - 1};
        if (cnt[pp] >= 0) {
          can.push_back(pp);
        }
      }

      pair<int, int> xy = can[randint(0, can.size() - 1)];
      u.push_back(i);
      v.push_back(j);
      a.push_back(xy.first);
      b.push_back(xy.second);
      cnt[xy] = -100;
      die(i, j);
    }
  }

  for (int i = 0; i < (int)u.size(); i++) {
    g[u[i]].push_back(v[i]);
    g[v[i]].push_back(u[i]);
  }
  used.assign(n, 0);
  dfs(0);
  assert(*min_element(used.begin(), used.end()) == 1);

  build(u, v, a, b);
  return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 851 ms 49424 KB Output is correct
10 Correct 41 ms 4952 KB Output is correct
11 Correct 280 ms 26024 KB Output is correct
12 Correct 70 ms 7364 KB Output is correct
13 Correct 101 ms 16268 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 944 KB Output is correct
16 Correct 858 ms 47068 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 851 ms 49424 KB Output is correct
10 Correct 41 ms 4952 KB Output is correct
11 Correct 280 ms 26024 KB Output is correct
12 Correct 70 ms 7364 KB Output is correct
13 Correct 101 ms 16268 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 944 KB Output is correct
16 Correct 858 ms 47068 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 3404 ms 90408 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Runtime error 9 ms 1356 KB Execution killed with signal 8
26 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 851 ms 49424 KB Output is correct
10 Correct 41 ms 4952 KB Output is correct
11 Correct 280 ms 26024 KB Output is correct
12 Correct 70 ms 7364 KB Output is correct
13 Correct 101 ms 16268 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 944 KB Output is correct
16 Correct 858 ms 47068 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 3404 ms 90408 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Runtime error 9 ms 1356 KB Execution killed with signal 8
26 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 851 ms 49424 KB Output is correct
10 Correct 41 ms 4952 KB Output is correct
11 Correct 280 ms 26024 KB Output is correct
12 Correct 70 ms 7364 KB Output is correct
13 Correct 101 ms 16268 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 944 KB Output is correct
16 Correct 858 ms 47068 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Runtime error 3119 ms 145232 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 851 ms 49424 KB Output is correct
10 Correct 41 ms 4952 KB Output is correct
11 Correct 280 ms 26024 KB Output is correct
12 Correct 70 ms 7364 KB Output is correct
13 Correct 101 ms 16268 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 944 KB Output is correct
16 Correct 858 ms 47068 KB Output is correct
17 Correct 2092 ms 102036 KB Output is correct
18 Correct 2114 ms 103240 KB Output is correct
19 Runtime error 3114 ms 145860 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 851 ms 49424 KB Output is correct
10 Correct 41 ms 4952 KB Output is correct
11 Correct 280 ms 26024 KB Output is correct
12 Correct 70 ms 7364 KB Output is correct
13 Correct 101 ms 16268 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 944 KB Output is correct
16 Correct 858 ms 47068 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 3404 ms 90408 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Runtime error 9 ms 1356 KB Execution killed with signal 8
26 Halted 0 ms 0 KB -