oj.uz

답안 #465692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465692 2021-08-16T16:30:55 Z alexxela12345 분수 공원 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -