oj.uz

Submission #468557

# Submission time Handle Problem Language Result Execution time Memory
468557 2021-08-28T17:25:31 Z fun_day Fountain Parks (IOI21_parks) C++17
5 / 100
 1354 ms 79032 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{
      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);
    }
    else{
      one.emplace_back(choice1.first);
      two.emplace_back(choice1.second);
    }
  }
  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 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 565 ms 39400 KB Output is correct
10 Correct 22 ms 4300 KB Output is correct
11 Correct 142 ms 21392 KB Output is correct
12 Correct 35 ms 6388 KB Output is correct
13 Correct 78 ms 13016 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 545 ms 39500 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 565 ms 39400 KB Output is correct
10 Correct 22 ms 4300 KB Output is correct
11 Correct 142 ms 21392 KB Output is correct
12 Correct 35 ms 6388 KB Output is correct
13 Correct 78 ms 13016 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 545 ms 39500 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 565 ms 39400 KB Output is correct
10 Correct 22 ms 4300 KB Output is correct
11 Correct 142 ms 21392 KB Output is correct
12 Correct 35 ms 6388 KB Output is correct
13 Correct 78 ms 13016 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 545 ms 39500 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 565 ms 39400 KB Output is correct
10 Correct 22 ms 4300 KB Output is correct
11 Correct 142 ms 21392 KB Output is correct
12 Correct 35 ms 6388 KB Output is correct
13 Correct 78 ms 13016 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 545 ms 39500 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Incorrect 1 ms 204 KB Tree @(199999, 199999) appears more than once: for edges on positions 0 and 1
19 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 565 ms 39400 KB Output is correct
10 Correct 22 ms 4300 KB Output is correct
11 Correct 142 ms 21392 KB Output is correct
12 Correct 35 ms 6388 KB Output is correct
13 Correct 78 ms 13016 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 545 ms 39500 KB Output is correct
17 Incorrect 1354 ms 79032 KB Tree @(100001, 100001) appears more than once: for edges on positions 130005 and 130006
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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 565 ms 39400 KB Output is correct
10 Correct 22 ms 4300 KB Output is correct
11 Correct 142 ms 21392 KB Output is correct
12 Correct 35 ms 6388 KB Output is correct
13 Correct 78 ms 13016 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 545 ms 39500 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -