oj.uz

Submission #601207

# Submission time Handle Problem Language Result Execution time Memory
601207 2022-07-21T13:09:12 Z MilosMilutinovic Fountain Parks (IOI21_parks) C++17
5 / 100
 613 ms 38108 KB 
/**
 *    author:  wxhtzdy
 *    created: 21.07.2022 14:34:57
**/
/* 
  First idea was 2SAT having verteces (road, direction), but there always exist constructive idea...
  https://oj.uz/submission/437652 
*/
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

const int dx[] = {2, 0, -2, 0};
const int dy[] = {0, 2, 0, -2};

class dsu {
  public:
  vector<int> p;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int construct_roads(vector<int> x, vector<int> y) {
  int n = (int) x.size();
  map<pair<int, int>, int> mp;
  for (int i = 0; i < n; i++) {
    mp[{x[i], y[i]}] = i;
  }
  vector<vector<int>> id(n, vector<int>(4, -1));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 4; j++) {
      int nx = x[i] + dx[j];
      int ny = y[i] + dy[j];
      if (mp.count({nx, ny})) {
        id[i][j] = mp[{nx, ny}];        
      }
    }
  }
  dsu d(n);
  vector<int> u, v;
  vector<int> a, b;
  auto Add = [&](int i, int j) {
    d.unite(i, j);
    u.push_back(i);
    v.push_back(j);
    if (x[i] == x[j]) {
      b.push_back(y[i] + y[j] >> 1);
      if ((x[i] + y[i]) % 2 == 1) {
        a.push_back(x[i] - 1);
      } else {
        a.push_back(x[i] + 1);
      }
    } else {
      a.push_back(x[i] + x[j] >> 1);
      if ((x[i] + y[i]) % 2 == 1) {
        b.push_back(y[i] + 1);
      } else {
        b.push_back(y[i] - 1);
      }
    }
  };
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return x[i] + y[i] > x[j] + y[j];
  });
  for (int i : order) {
    int i0 = id[i][0], i1 = id[i][1];
    if (i0 == -1 && i1 == -1) {
      continue;
    }
    if (i0 == -1) {
      Add(i, i1);
      continue;
    }
    if (i1 == -1) {
      Add(i, i0);
      continue;
    }
    if (d.get(i0) != d.get(i1)) {
      Add(i, i0);
      Add(i, i1);
    } else {
      if ((x[i] + y[i]) % 2 == 1) {
        Add(i, i0);
      } else {
        Add(i, i1);
      }
    }
  }
  if ((int) u.size() != n - 1) {
    return 0;    
  }
  build(u, v, a, b);
  return 1;
}

Compilation message

parks.cpp: In lambda function:
parks.cpp:63:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |       b.push_back(y[i] + y[j] >> 1);
parks.cpp:70:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |       a.push_back(x[i] + x[j] >> 1);

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 176 ms 19212 KB Output is correct
10 Correct 14 ms 2260 KB Output is correct
11 Correct 68 ms 10524 KB Output is correct
12 Correct 18 ms 3120 KB Output is correct
13 Correct 47 ms 7332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 210 ms 19204 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 176 ms 19212 KB Output is correct
10 Correct 14 ms 2260 KB Output is correct
11 Correct 68 ms 10524 KB Output is correct
12 Correct 18 ms 3120 KB Output is correct
13 Correct 47 ms 7332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 210 ms 19204 KB Output is correct
17 Incorrect 0 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 176 ms 19212 KB Output is correct
10 Correct 14 ms 2260 KB Output is correct
11 Correct 68 ms 10524 KB Output is correct
12 Correct 18 ms 3120 KB Output is correct
13 Correct 47 ms 7332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 210 ms 19204 KB Output is correct
17 Incorrect 0 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 176 ms 19212 KB Output is correct
10 Correct 14 ms 2260 KB Output is correct
11 Correct 68 ms 10524 KB Output is correct
12 Correct 18 ms 3120 KB Output is correct
13 Correct 47 ms 7332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 210 ms 19204 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 613 ms 38008 KB Output is correct
21 Incorrect 566 ms 38108 KB Tree @(99999, 100003) appears more than once: for edges on positions 0 and 2
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 176 ms 19212 KB Output is correct
10 Correct 14 ms 2260 KB Output is correct
11 Correct 68 ms 10524 KB Output is correct
12 Correct 18 ms 3120 KB Output is correct
13 Correct 47 ms 7332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 210 ms 19204 KB Output is correct
17 Incorrect 555 ms 38048 KB Tree @(3, 100001) appears more than once: for edges on positions 99999 and 100000
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 176 ms 19212 KB Output is correct
10 Correct 14 ms 2260 KB Output is correct
11 Correct 68 ms 10524 KB Output is correct
12 Correct 18 ms 3120 KB Output is correct
13 Correct 47 ms 7332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 210 ms 19204 KB Output is correct
17 Incorrect 0 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -