oj.uz

Submission #468559

# Submission time Handle Problem Language Result Execution time Memory
468559 2021-08-28T17:29:05 Z fun_day Fountain Parks (IOI21_parks) C++17
5 / 100
 1492 ms 79300 KB 
#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

struct Edge {
  int from , to , cost;
  bool operator<(const Edge &autre){
    if(from == autre.from){
      return to < autre.to;
    }
    return from < autre.from;
  }
}; 

const int N = 1e5 * 2 + 10;
int p[N];
int sz[N];

void make(int a){
  p[a] = a;
  sz[a] = 1;
  return ;
}

int find_set(int a){
  if(p[a] == a) return a;
  return p[a] = find_set(p[a]);
}

bool union_sets(int a , int b){
  a = find_set(a);
  b = find_set(b);
  if(a == b) return false;
  if(sz[a] < sz[b]) swap(a,b);
  p[b] = a;
  sz[a] += sz[b];
  return true;
}

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

int construct_roads(vector<int> x , vector<int> y){
  int n = (int)x.size();
  if(n == 1){
    build({} , {} , {} , {});
    return 1;
  }
  map<pair<int,int> , int> seen;
  map<int , pair<int,int>> after;
  for(int i = 0 ; i < n ; i++){
    seen[make_pair(x[i] , y[i])] = i + 1;
    after[i] = make_pair(x[i] , y[i]);
  }
  for(int i = 0 ; i < n ; i++){
    make(i);
  }
  vector<int> u  , q;
  for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < 4 ; j++){
      int new_x = x[i] + dx[j];
      int new_y = y[i] + dy[j];
      int m = seen[make_pair(new_x , new_y)];
      if(m){
        m--;
        if(union_sets(i , m)){
          u.emplace_back(i);
          q.emplace_back(m);          
        }
      }
    }
  }
  if(sz[find_set(0)] != n) return 0;
  map<pair<int,int> , bool> used;
  vector<int> one , two;
  for(int i = 0 ; i < (int)u.size() ; i++){
    int now_t = u[i] , now_z = q[i];
    auto pq = after[now_t] , r = after[now_z];
    pair<int,int> choice1 , choice2;
    if(pq.first == r.first){
      choice1 = make_pair(pq.first - 1 , (pq.second+r.second)/2);
      choice2 = make_pair(pq.first + 1 , (pq.second+r.second)/2);
    }
    else{
      assert(pq.second == r.second);
      choice1 = make_pair((pq.first + r.first)/2 , pq.second - 1);
      choice2 = make_pair((pq.first + r.first) / 2 , pq.second + 1);
    }
    if(used[choice1]){
      one.emplace_back(choice2.first);
      two.emplace_back(choice2.second);
      used[choice2] = true;
    }
    else{
      one.emplace_back(choice1.first);
      two.emplace_back(choice1.second);
      used[choice1] = true;
    }
  }
  build(u , q , one , two);
  return 1;
}
/*int main(){
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  for(int i = 0 ; i < n ; i++){
    cin >> x[i];
  }
  for(int i = 0 ; i < n ; i++){
    cin >> y[i];
  }
  cout << construct_roads(x , y);
  return 0;
} */

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 1 ms 204 KB Output is correct
4 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 563 ms 38648 KB Output is correct
10 Correct 26 ms 4208 KB Output is correct
11 Correct 144 ms 20896 KB Output is correct
12 Correct 37 ms 6272 KB Output is correct
13 Correct 77 ms 12696 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 584 ms 38708 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 1 ms 204 KB Output is correct
4 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 563 ms 38648 KB Output is correct
10 Correct 26 ms 4208 KB Output is correct
11 Correct 144 ms 20896 KB Output is correct
12 Correct 37 ms 6272 KB Output is correct
13 Correct 77 ms 12696 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 584 ms 38708 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Incorrect 1 ms 296 KB Tree @(3, 5) appears more than once: for edges on positions 2 and 6
21 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 1 ms 204 KB Output is correct
4 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 563 ms 38648 KB Output is correct
10 Correct 26 ms 4208 KB Output is correct
11 Correct 144 ms 20896 KB Output is correct
12 Correct 37 ms 6272 KB Output is correct
13 Correct 77 ms 12696 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 584 ms 38708 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Incorrect 1 ms 296 KB Tree @(3, 5) appears more than once: for edges on positions 2 and 6
21 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 1 ms 204 KB Output is correct
4 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 563 ms 38648 KB Output is correct
10 Correct 26 ms 4208 KB Output is correct
11 Correct 144 ms 20896 KB Output is correct
12 Correct 37 ms 6272 KB Output is correct
13 Correct 77 ms 12696 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 584 ms 38708 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Incorrect 1366 ms 65128 KB Tree @(178467, 21537) appears more than once: for edges on positions 3048 and 3049
21 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 1 ms 204 KB Output is correct
4 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 563 ms 38648 KB Output is correct
10 Correct 26 ms 4208 KB Output is correct
11 Correct 144 ms 20896 KB Output is correct
12 Correct 37 ms 6272 KB Output is correct
13 Correct 77 ms 12696 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 584 ms 38708 KB Output is correct
17 Correct 1492 ms 77036 KB Output is correct
18 Incorrect 1388 ms 79300 KB Tree @(50003, 50001) appears more than once: for edges on positions 137260 and 163930
19 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 1 ms 204 KB Output is correct
4 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 563 ms 38648 KB Output is correct
10 Correct 26 ms 4208 KB Output is correct
11 Correct 144 ms 20896 KB Output is correct
12 Correct 37 ms 6272 KB Output is correct
13 Correct 77 ms 12696 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 4 ms 844 KB Output is correct
16 Correct 584 ms 38708 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Incorrect 1 ms 296 KB Tree @(3, 5) appears more than once: for edges on positions 2 and 6
21 Halted 0 ms 0 KB -