oj.uz

Submission #468561

# Submission time Handle Problem Language Result Execution time Memory
468561 2021-08-28T17:31:35 Z fun_day Fountain Parks (IOI21_parks) C++17
5 / 100
 1400 ms 77436 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(choice1.first);
      two.emplace_back(choice1.second);
      used[choice1] = true;
    }
    else if(!used[choice2]){
      one.emplace_back(choice2.first);
      two.emplace_back(choice2.second);
      used[choice2] = 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 0 ms 204 KB Output is correct
2 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 603 ms 38872 KB Output is correct
10 Correct 23 ms 4300 KB Output is correct
11 Correct 147 ms 21164 KB Output is correct
12 Correct 36 ms 6412 KB Output is correct
13 Correct 81 ms 12876 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 574 ms 38788 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 603 ms 38872 KB Output is correct
10 Correct 23 ms 4300 KB Output is correct
11 Correct 147 ms 21164 KB Output is correct
12 Correct 36 ms 6412 KB Output is correct
13 Correct 81 ms 12876 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 574 ms 38788 KB Output is correct
17 Correct 1 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 0 ms 204 KB Wrong answer detected in grader
21 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 603 ms 38872 KB Output is correct
10 Correct 23 ms 4300 KB Output is correct
11 Correct 147 ms 21164 KB Output is correct
12 Correct 36 ms 6412 KB Output is correct
13 Correct 81 ms 12876 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 574 ms 38788 KB Output is correct
17 Correct 1 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 0 ms 204 KB Wrong answer detected in grader
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 603 ms 38872 KB Output is correct
10 Correct 23 ms 4300 KB Output is correct
11 Correct 147 ms 21164 KB Output is correct
12 Correct 36 ms 6412 KB Output is correct
13 Correct 81 ms 12876 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 574 ms 38788 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Incorrect 1126 ms 59236 KB Wrong answer detected in grader
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 603 ms 38872 KB Output is correct
10 Correct 23 ms 4300 KB Output is correct
11 Correct 147 ms 21164 KB Output is correct
12 Correct 36 ms 6412 KB Output is correct
13 Correct 81 ms 12876 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 574 ms 38788 KB Output is correct
17 Correct 1400 ms 77436 KB Output is correct
18 Incorrect 1159 ms 73816 KB Wrong answer detected in grader
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 603 ms 38872 KB Output is correct
10 Correct 23 ms 4300 KB Output is correct
11 Correct 147 ms 21164 KB Output is correct
12 Correct 36 ms 6412 KB Output is correct
13 Correct 81 ms 12876 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 3 ms 844 KB Output is correct
16 Correct 574 ms 38788 KB Output is correct
17 Correct 1 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 0 ms 204 KB Wrong answer detected in grader
21 Halted 0 ms 0 KB -