oj.uz

Submission #492855

# Submission time Handle Problem Language Result Execution time Memory
492855 2021-12-09T10:50:48 Z Sunset Fountain Parks (IOI21_parks) C++17
5 / 100
 689 ms 71756 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) ((int)(x).size())

using namespace std;
typedef pair<int, int> ipair;
const ipair D[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

ipair operator + (ipair const& a, ipair const& b) { return {a.X+b.X, a.Y+b.Y}; }
ipair operator - (ipair const& a, ipair const& b) { return {a.X-b.X, a.Y-b.Y}; }
ipair operator * (ipair const& a, int b) { return {a.X*b, a.Y*b}; }

int construct_roads(std::vector<int> ix, std::vector<int> iy) {
  int n = sz(ix);
  map<ipair, int> fs;
  set<pair<ipair, ipair>> roads;
  for (int i = 0; i < n; ++i)
    fs[{ix[i], iy[i]}] = i;

  vector<int> ansA, ansB, ansX, ansY;

  set<ipair> q;
  set<ipair> vis;
  set<ipair> done;
  q.insert({ix[0], iy[0]});
  vis.insert({ix[0], iy[0]});

  bool isFirst = true;
  while (!q.empty()) {
    ipair p = *q.begin();
    q.erase(p);

    if (!isFirst) {
      for (int i = 0; i < 4; ++i) {
        ipair d = D[i];
        ipair p2 = p + d * 2;
        if (!done.count(p2)) continue;
        ipair d2;
        if ((p.X + p.Y) & 1) {
          d2 = D[(i + 1) % 4];
        } else {
          d2 = D[(i + 3) % 4];
        }
        if (roads.count({p + d2 * 2, p2 + d2 * 2})) continue;
        roads.insert({p, p2});
        roads.insert({p2, p});
        ansA.push_back(fs[p]);
        ansB.push_back(fs[p2]);
        ipair pp = p + d + d2;
        ansX.push_back(pp.X);
        ansY.push_back(pp.Y);
        break;
      }
    }
    isFirst = false;
    done.insert(p);

    for (auto d : D)
      if (fs.count(p + d * 2) && !vis.count(p + d * 2)) {
        q.insert(p + d * 2);
        vis.insert(p + d * 2);
      }
  }

  if (sz(vis) != n) return 0;
  build(ansA, ansB, ansX, ansY);
  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 0 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 0 ms 204 KB Output is correct
9 Correct 312 ms 35540 KB Output is correct
10 Correct 22 ms 3960 KB Output is correct
11 Correct 158 ms 19264 KB Output is correct
12 Correct 36 ms 5832 KB Output is correct
13 Correct 77 ms 11204 KB Output is correct
14 Correct 1 ms 424 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 35560 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 0 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 0 ms 204 KB Output is correct
9 Correct 312 ms 35540 KB Output is correct
10 Correct 22 ms 3960 KB Output is correct
11 Correct 158 ms 19264 KB Output is correct
12 Correct 36 ms 5832 KB Output is correct
13 Correct 77 ms 11204 KB Output is correct
14 Correct 1 ms 424 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 35560 KB Output is correct
17 Incorrect 0 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 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 0 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 0 ms 204 KB Output is correct
9 Correct 312 ms 35540 KB Output is correct
10 Correct 22 ms 3960 KB Output is correct
11 Correct 158 ms 19264 KB Output is correct
12 Correct 36 ms 5832 KB Output is correct
13 Correct 77 ms 11204 KB Output is correct
14 Correct 1 ms 424 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 35560 KB Output is correct
17 Incorrect 0 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 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 0 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 0 ms 204 KB Output is correct
9 Correct 312 ms 35540 KB Output is correct
10 Correct 22 ms 3960 KB Output is correct
11 Correct 158 ms 19264 KB Output is correct
12 Correct 36 ms 5832 KB Output is correct
13 Correct 77 ms 11204 KB Output is correct
14 Correct 1 ms 424 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 35560 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Incorrect 689 ms 71756 KB Tree @(195229, 4773) appears more than once: for edges on positions 1 and 2
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 0 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 0 ms 204 KB Output is correct
9 Correct 312 ms 35540 KB Output is correct
10 Correct 22 ms 3960 KB Output is correct
11 Correct 158 ms 19264 KB Output is correct
12 Correct 36 ms 5832 KB Output is correct
13 Correct 77 ms 11204 KB Output is correct
14 Correct 1 ms 424 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 35560 KB Output is correct
17 Incorrect 648 ms 71292 KB Tree @(3, 100001) appears more than once: for edges on positions 41209 and 41210
18 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 0 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 0 ms 204 KB Output is correct
9 Correct 312 ms 35540 KB Output is correct
10 Correct 22 ms 3960 KB Output is correct
11 Correct 158 ms 19264 KB Output is correct
12 Correct 36 ms 5832 KB Output is correct
13 Correct 77 ms 11204 KB Output is correct
14 Correct 1 ms 424 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 35560 KB Output is correct
17 Incorrect 0 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -