oj.uz

답안 #468557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468557 2021-08-28T17:25:31 Z fun_day 분수 공원 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -