제출 #1300500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300500		lizi14	Obstacles for a Llama (IOI25_obstacles)	C++20	13 / 100	70 ms	16216 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int>k;
vector<int>h;
int x[3][N];
int ixvi[3][N];
long long n,bati;

//const int N=2e5+5;
vector<int>v[N];
vector<pair<int,int>>p;
void make_set(int w){
    p[w].first=w;
    p[w].second=1;
    // parent[v]=v;
    // size[v]=1;
}

int rec(int w){
    if(w!=p[w].first) {
        //int len=p[w].second;
        p[w].first=rec(p[w].first);
        //p[w].second+=len;
    }
    return p[w].first;
}

void gaertianeba(int u,int w){
    int k=rec(u);
    int h=rec(w);
    if(k!=h){
        if(p[k].second>=p[h].second){
            //v[k].push_back(h);
            p[k].second+=p[h].second;
            p[h].first=k;
        }
        else{
            //v[h].push_back(k);
            p[h].second+=p[k].second;
            p[k].first=h;
        }
    }
    return;
}

void initialize(vector<int> T, vector<int> H) {
    n=H.size();
    int j=0;
    bati=T.size();
    for(int j=0; j<H.size(); j++){
        if(T[0]<=H[j]){
            //x[j]=-1;
            k.push_back(j);
        }
        else{
            //x[j]=1;
        }
        //cout<<x[j]<<" ";
        //x[j]=a;
        //j++;
    }
    for(int i=0; i<H.size(); i++){
        if(T[bati-1]<=H[i]){
            h.push_back(i);
            //x[i]=-1;
        }
    }
    if(bati==3){
        p.assign(3*n, {0,0});
        for(int i=0; i<3; i++){
            for(int j=0; j<n; j++){
                x[i][j]=i*n+j;
                if(T[i]<=H[j]){
                    ixvi[i][j]=-1;
                }
                else ixvi[i][j]=1;
            }
        }
        
        for(int i=0; i<bati; i++){
            for(int j=0; j<n; j++){
                make_set(x[i][j]);
            }
        }
        for(int i=0; i<bati; i++){
            for(int j=0; j<n; j++){
                if(ixvi[i][j]!=-1){
                    if(i>0){
                        if(ixvi[i-1][j]!=-1){
                            gaertianeba(x[i-1][j],x[i][j]);
                        }
                    }
                    if(j>0){
                        if(ixvi[i][j-1]!=-1){
                            gaertianeba(x[i][j-1],x[i][j]);
                        }
                    }
                }
                
            }
        }
        
    }
    return;
}

bool can_reach(int L, int R, int S, int D) {
    //L--,R--,S--,D--;
    if(S>D)swap(S,D);
    int s_id=x[0][S];
    int d_id=x[0][D];
    int k=rec(s_id);
    int h=rec(d_id);
    if(k==h){
        return true;
    }
    else{
        return 0;
    }
    
}

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