oj.uz

답안 #465820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465820 2021-08-16T19:24:34 Z alexxela12345 분수 공원 (IOI21_parks) C++17
5 / 100
 3103 ms 145964 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);
      merge(i, 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});
      }
    }
    assert(kek.size() == alive.size());
    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);
        }
      }
      if (can.empty()) {
        return 0;
      }
      pair<int, int> xy = can[randint(0, can.size() - 1)];
      u.push_back(i);
      v.push_back(j);
      merge(i, 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

# 결과 실행 시간 메모리 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 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 884 ms 49644 KB Output is correct
10 Correct 41 ms 4940 KB Output is correct
11 Correct 282 ms 26020 KB Output is correct
12 Correct 66 ms 7340 KB Output is correct
13 Correct 97 ms 16120 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 868 ms 46988 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 884 ms 49644 KB Output is correct
10 Correct 41 ms 4940 KB Output is correct
11 Correct 282 ms 26020 KB Output is correct
12 Correct 66 ms 7340 KB Output is correct
13 Correct 97 ms 16120 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 868 ms 46988 KB Output is correct
17 Correct 0 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 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 2472 ms 92024 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 5 ms 716 KB Output is correct
26 Correct 7 ms 1228 KB Output is correct
27 Correct 10 ms 1484 KB Output is correct
28 Correct 799 ms 35588 KB Output is correct
29 Correct 1310 ms 54336 KB Output is correct
30 Correct 1928 ms 70052 KB Output is correct
31 Correct 2522 ms 91408 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 6 ms 844 KB Output is correct
44 Correct 6 ms 1100 KB Output is correct
45 Runtime error 3064 ms 73760 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 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 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 884 ms 49644 KB Output is correct
10 Correct 41 ms 4940 KB Output is correct
11 Correct 282 ms 26020 KB Output is correct
12 Correct 66 ms 7340 KB Output is correct
13 Correct 97 ms 16120 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 868 ms 46988 KB Output is correct
17 Correct 0 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 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 2472 ms 92024 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 5 ms 716 KB Output is correct
26 Correct 7 ms 1228 KB Output is correct
27 Correct 10 ms 1484 KB Output is correct
28 Correct 799 ms 35588 KB Output is correct
29 Correct 1310 ms 54336 KB Output is correct
30 Correct 1928 ms 70052 KB Output is correct
31 Correct 2522 ms 91408 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 6 ms 844 KB Output is correct
44 Correct 6 ms 1100 KB Output is correct
45 Runtime error 3064 ms 73760 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 884 ms 49644 KB Output is correct
10 Correct 41 ms 4940 KB Output is correct
11 Correct 282 ms 26020 KB Output is correct
12 Correct 66 ms 7340 KB Output is correct
13 Correct 97 ms 16120 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 868 ms 46988 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 3102 ms 145416 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 884 ms 49644 KB Output is correct
10 Correct 41 ms 4940 KB Output is correct
11 Correct 282 ms 26020 KB Output is correct
12 Correct 66 ms 7340 KB Output is correct
13 Correct 97 ms 16120 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 868 ms 46988 KB Output is correct
17 Correct 2084 ms 99756 KB Output is correct
18 Correct 2113 ms 103276 KB Output is correct
19 Runtime error 3103 ms 145964 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 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 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 884 ms 49644 KB Output is correct
10 Correct 41 ms 4940 KB Output is correct
11 Correct 282 ms 26020 KB Output is correct
12 Correct 66 ms 7340 KB Output is correct
13 Correct 97 ms 16120 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 868 ms 46988 KB Output is correct
17 Correct 0 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 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 2472 ms 92024 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 5 ms 716 KB Output is correct
26 Correct 7 ms 1228 KB Output is correct
27 Correct 10 ms 1484 KB Output is correct
28 Correct 799 ms 35588 KB Output is correct
29 Correct 1310 ms 54336 KB Output is correct
30 Correct 1928 ms 70052 KB Output is correct
31 Correct 2522 ms 91408 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 6 ms 844 KB Output is correct
44 Correct 6 ms 1100 KB Output is correct
45 Runtime error 3064 ms 73760 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -