oj.uz

Submission #465692

# Submission time Handle Problem Language Result Execution time Memory
465692 2021-08-16T16:30:55 Z alexxela12345 Fountain Parks (IOI21_parks) C++17
5 / 100
 707 ms 51556 KB 
#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

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<int> u, v, a, b;
    vector<vector<int>> g(n);
    auto add = [&](int i, int j) {
      if (i < j) {
	g[i].push_back(j);
	g[j].push_back(i);
        u.push_back(i);
        v.push_back(j);
        if (x[i] != x[j]) {
	  a.push_back((x[i] + x[j]) / 2);
	  b.push_back(y[i] + 1);
        } else {
	  b.push_back((y[i] + y[j]) / 2);
	  if (x[i] == 2) {
	    a.push_back(1);
          } else {
            a.push_back(3);
          }
        }
      }
    };

    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;
    }
    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 292 KB Output is correct
9 Correct 242 ms 25300 KB Output is correct
10 Correct 15 ms 2784 KB Output is correct
11 Correct 85 ms 14008 KB Output is correct
12 Correct 23 ms 4056 KB Output is correct
13 Correct 60 ms 9292 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 298 ms 22644 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 292 KB Output is correct
9 Correct 242 ms 25300 KB Output is correct
10 Correct 15 ms 2784 KB Output is correct
11 Correct 85 ms 14008 KB Output is correct
12 Correct 23 ms 4056 KB Output is correct
13 Correct 60 ms 9292 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 298 ms 22644 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 3
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 292 KB Output is correct
9 Correct 242 ms 25300 KB Output is correct
10 Correct 15 ms 2784 KB Output is correct
11 Correct 85 ms 14008 KB Output is correct
12 Correct 23 ms 4056 KB Output is correct
13 Correct 60 ms 9292 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 298 ms 22644 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 3
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 292 KB Output is correct
9 Correct 242 ms 25300 KB Output is correct
10 Correct 15 ms 2784 KB Output is correct
11 Correct 85 ms 14008 KB Output is correct
12 Correct 23 ms 4056 KB Output is correct
13 Correct 60 ms 9292 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 298 ms 22644 KB Output is correct
17 Incorrect 1 ms 204 KB Tree (a[0], b[0]) = (3, 3) is not adjacent to edge between u[0]=0 @(200000, 2) and v[0]=1 @(200000, 4)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 292 KB Output is correct
9 Correct 242 ms 25300 KB Output is correct
10 Correct 15 ms 2784 KB Output is correct
11 Correct 85 ms 14008 KB Output is correct
12 Correct 23 ms 4056 KB Output is correct
13 Correct 60 ms 9292 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 298 ms 22644 KB Output is correct
17 Incorrect 707 ms 51556 KB Tree (a[2], b[2]) = (3, 52499) is not adjacent to edge between u[2]=1 @(100002, 52498) and v[2]=117727 @(100002, 52500)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 292 KB Output is correct
9 Correct 242 ms 25300 KB Output is correct
10 Correct 15 ms 2784 KB Output is correct
11 Correct 85 ms 14008 KB Output is correct
12 Correct 23 ms 4056 KB Output is correct
13 Correct 60 ms 9292 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 298 ms 22644 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 3
18 Halted 0 ms 0 KB -