제출 #1252469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252469		Jakub_Wozniak	장애물 (IOI25_obstacles)	C++20	23 / 100	2095 ms	9288 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200009;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
int N , M;
bool czy[maxn];
int t[maxn][3];
bool czyp[maxn];

int find(int x , int poz)
{
  if(t[x][poz] == x)return x;
  return t[x][poz] = find(t[x][poz] , poz);
}

void union_(int a , int b ,int poz)
{
  a = find(a,poz);
  b = find(b,poz);
  if(a == b)return ;
  t[a][poz] = b;
}

void initialize(std::vector<int> T, std::vector<int> H) 
{
  N = T.size();
  M = H.size();

  for(int i = 0 ; i < M ; i++)for(int poz = 0 ; poz < N ; poz++)t[i][poz] = i;

  for(int poz = 0 ; poz < N ; poz++)for(int i = 0 ; i < M ; i++)
  {
    czy[i] = 0;
    if(T[poz] > H[i])
    {
      czy[i] = 1;
    }
    else continue;

    if(poz == 1)
    {
      czyp[find(i,poz-1)] = 1;
    }

    if((i != 0) && (czy[i-1]))union_(i,i-1 , poz);
  }
  return;
}

bool can_reach(int L, int R, int S, int D) 
{
  return ((find(S,0) == find(D,0)) || (czyp[find(D,0)] && czyp[find(S,0)] && find(S,2) == find(D,2)));
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17