제출 #1306574

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

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long


vector<vector<int>> grid;
int n,m; //N=2 for subtask 2
vector<int> DX = {-1,1,0,0};
vector<int> DY = {0,0,-1,1};

class DSU {
public:
    int n0;
    vector<int> par;
    vector<int> size;
    DSU(int sz) {
        n0 = sz;
        size = vector<int>(n0,1);
        par=vector<int>(n0); iota(par.begin(), par.end(), (int)0);
    }
    int find(int u) {
        if (u==par[u]) return u;
        return par[u] = find(par[u]);
    }
    void link(int u, int v) {
        u = find(u); v = find(v);
        if (size[u]<size[v]) swap(u,v);
        if (u==v) return; //skip
        size[u] += size[v]; size[v] = 0; par[v] = u;
    }
};

DSU dsu(0);

void initialize(std::vector<signed> T, std::vector<signed> H) {
    //subtask 1, 3
    n = T.size(); 
    m = H.size();
    assert(n*m<1000000);
    grid = vector<vector<int>>(n, vector<int>(m,0));
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            grid[i][j] = T[i] > H[j];
        }
    }
    dsu = DSU(n*m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (grid[i][j]==0) continue;
            for (int d=0; d<4; d++) {
                int ni = i + DX[d];
                int nj = j + DY[d];
                if (0<=ni && ni<n && 0<=nj && nj<m) {
                    if (grid[ni][nj] == 1) dsu.link(m*i+j, m*ni+nj);
                }
            }
        }
    }
    return;
}

bool can_reach(signed L, signed R, signed S, signed D) {
    assert(L==0);
    assert(R==m-1);
    //check that (0, S) and (0, D) are in the same component, this is fine because the IDs are 0*m+S, 0*m+D
    bool connected = dsu.find(S) == dsu.find(D);
    return connected;
}

• 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