Submission #601211

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
601211	2022-07-21T13:11:44 Z	MilosMilutinovic	Fountain Parks (IOI21_parks)	C++17	5 / 100	615 ms	39580 KB

parks

/**
 *    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 == 0) {
        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	0 ms	212 KB	Output is correct
3	Correct	0 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	179 ms	19232 KB	Output is correct
10	Correct	11 ms	2260 KB	Output is correct
11	Correct	72 ms	10524 KB	Output is correct
12	Correct	19 ms	3092 KB	Output is correct
13	Correct	43 ms	7372 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	596 KB	Output is correct
16	Correct	179 ms	19168 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	0 ms	212 KB	Output is correct
3	Correct	0 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	179 ms	19232 KB	Output is correct
10	Correct	11 ms	2260 KB	Output is correct
11	Correct	72 ms	10524 KB	Output is correct
12	Correct	19 ms	3092 KB	Output is correct
13	Correct	43 ms	7372 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	596 KB	Output is correct
16	Correct	179 ms	19168 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	599 ms	39580 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	2 ms	468 KB	Output is correct
26	Correct	4 ms	724 KB	Output is correct
27	Correct	5 ms	980 KB	Output is correct
28	Correct	160 ms	16024 KB	Output is correct
29	Incorrect	292 ms	24116 KB	Tree @(3, 80003) appears more than once: for edges on positions 119996 and 119997
30	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	0 ms	212 KB	Output is correct
3	Correct	0 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	179 ms	19232 KB	Output is correct
10	Correct	11 ms	2260 KB	Output is correct
11	Correct	72 ms	10524 KB	Output is correct
12	Correct	19 ms	3092 KB	Output is correct
13	Correct	43 ms	7372 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	596 KB	Output is correct
16	Correct	179 ms	19168 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	599 ms	39580 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	2 ms	468 KB	Output is correct
26	Correct	4 ms	724 KB	Output is correct
27	Correct	5 ms	980 KB	Output is correct
28	Correct	160 ms	16024 KB	Output is correct
29	Incorrect	292 ms	24116 KB	Tree @(3, 80003) appears more than once: for edges on positions 119996 and 119997
30	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	0 ms	212 KB	Output is correct
3	Correct	0 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	179 ms	19232 KB	Output is correct
10	Correct	11 ms	2260 KB	Output is correct
11	Correct	72 ms	10524 KB	Output is correct
12	Correct	19 ms	3092 KB	Output is correct
13	Correct	43 ms	7372 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	596 KB	Output is correct
16	Correct	179 ms	19168 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	615 ms	38012 KB	Output is correct
21	Incorrect	598 ms	37944 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	0 ms	212 KB	Output is correct
3	Correct	0 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	179 ms	19232 KB	Output is correct
10	Correct	11 ms	2260 KB	Output is correct
11	Correct	72 ms	10524 KB	Output is correct
12	Correct	19 ms	3092 KB	Output is correct
13	Correct	43 ms	7372 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	596 KB	Output is correct
16	Correct	179 ms	19168 KB	Output is correct
17	Incorrect	522 ms	37972 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	0 ms	212 KB	Output is correct
3	Correct	0 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	179 ms	19232 KB	Output is correct
10	Correct	11 ms	2260 KB	Output is correct
11	Correct	72 ms	10524 KB	Output is correct
12	Correct	19 ms	3092 KB	Output is correct
13	Correct	43 ms	7372 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	596 KB	Output is correct
16	Correct	179 ms	19168 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	599 ms	39580 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	2 ms	468 KB	Output is correct
26	Correct	4 ms	724 KB	Output is correct
27	Correct	5 ms	980 KB	Output is correct
28	Correct	160 ms	16024 KB	Output is correct
29	Incorrect	292 ms	24116 KB	Tree @(3, 80003) appears more than once: for edges on positions 119996 and 119997
30	Halted	0 ms	0 KB	-

Submission #601211

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0

Subtask #6
0 / 30.0