DID : PS 2문제 (2023/04/04)

중간고사 6일 남았는데 미쳤다고 이러고 있네

BOJ 1920 수 찾기간단한 이분탐색 문제.
머지 소트랑 이분탐색 감을 살리려고 한번 풀었다.

//BOJ 1920 수 찾기
#include<bits/stdc++.h>
using namespace std;
int arr[(int)1e5 + 7], tmp[(int)1e5+7];
void merge_sort(int s,int e)
{
    //printf("%d %d\n", s,e);
    if(s == e) return;

    int mid = (s+e)/2;
    merge_sort(s,mid);
    merge_sort(mid+1, e);

    int i = s, j = mid+1, t = s;
    while(t <= e)
    {
        if(i > mid) tmp[t++] = arr[j++];
        else if(j > e) tmp[t++] = arr[i++];
        else tmp[t++] = (arr[i] < arr[j])?arr[i++] : arr[j++];
    }
    for(t = s; t <= e; t++) arr[t] = tmp[t];
}
bool f(int s,int e, int t)
{
    if(s == e) return arr[s] == t;

    int mid = (s+e)/2;
    return (t <= arr[mid]) ? f(s, mid, t) : f(mid+1, e, t);
}
int main()
{
    int n; scanf("%d", &n);
    for(int i = 1; i<= n; i++) scanf("%d", &arr[i]);
    merge_sort(1,n);

    int m; scanf("%d", &m);
    for(int i = 1; i<= m; i++)
    {
        int t; scanf("%d", &t);
        printf("%d\n", f(1,n,t));
    }
}

BOJ 1396 크루스칼의 공
안 간단한 문제. 이분탐색 -> 병렬 이분 탐색(PBS) -> 크루스칼의 공 순서로 검색하게 되어 풀어 보았다. 혼자 생각했을 때는 UF를 이용해서 O(M(logN+Q)) 풀이를 생각할 수 있었다. 아무리 생각해봐도 시간복잡도를 줄일 수가 없어서 기브업했다.

두가지 풀이가 있었는데 하나는 UF + PBS, 하나는 UF + LCA이다.
전자는 오프라인 쿼리로 풀고, 후자는 온라인 쿼리로 푸는데, 온라인 쿼리로 푸는게 신기해서 후자로 풀어보았다. 공부해 본다는 PBS는 아직 제대로 못봤고, 다음에 이걸로 다시 풀어봐야겠다. (+ PBS 연습문제 : BOJ 16977, BOJ 15957)

//BOJ 1396 크루스칼의 공
#include<bits/stdc++.h>
#define vii vector<pair<int,int> >
using namespace std;

vector<pair<int, pair<int,int> > > edgelist;
int parent[(int)2e5 + 7], troot[(int)2e5 + 7], used; //used : 마지막 정점의 번호, troot : tmproot
int depth[(int)2e5+7], weight[(int)2e5+7];
int snn[(int)2e5+7]; //snn : subtree node number
pair<int, int> tc[(int)2e5+7]; //tc : two children
void dfs(int d, int node)
{
    //if(node) printf(";%d\n", node);
    depth[node] = d;
    if(tc[node].first == -1) return;
    dfs(d+1, tc[node].first);
    dfs(d+1, tc[node].second);
}
int root(int a)
{
    //printf(":%d\n", a);
    if(troot[a] == a) return a;
    return troot[a] = root(troot[a]);
}


int lca[(int)2e5+7][25];
void lcainit(int n)
{
    for(int i = 0; i<= 20; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(!i) lca[j][i] = parent[j];
            else lca[j][i] = lca[lca[j][i-1]][i-1];
            //printf("%d ", lca[j][i]);
        }
        //printf("\n");
    }
}
int LCA(int a,int b)
{
    if(depth[a] < depth[b]) a=a+b, b=a-b, a=a-b;

    int t = 20;
    while(t--)
        if(depth[lca[a][t]] >= depth[b])
            a = lca[a][t];
    //printf("depthequal : %d %d\n", a,b);

    t = 20;
    if(a == b) return a;
    while(t--)
        if(lca[a][t] != lca[b][t])
            a = lca[a][t], b = lca[b][t];
    a = parent[a];
    b = parent[b];

    if(a == b) return a;
    else return -1;
}
int main()
{
    int n,m; scanf("%d %d", &n,&m);
    for(int i = 1; i <= m; i++)
    {
        int a,b,c; scanf("%d %d %d", &a,&b,&c);

        edgelist.push_back({c,{a,b}});
    }

    for(int i = 1; i <= n; i++) snn[i] = 1, tc[i] = {-1,-1}, troot[i] = parent[i] = i;

    used = n;
    sort(edgelist.begin(), edgelist.end());
    for(auto i : edgelist)
    {
        used++;
        int ra = root(i.second.first), rb = root(i.second.second);
        if(ra == rb) continue;

        parent[ra] = parent[rb] = parent[used] = used;
        troot[ra] = troot[rb] = troot[used] = used;
        troot[i.second.first] = troot[i.second.second] = used;
        weight[used] = i.first;

        snn[used] = snn[ra] + snn[rb];

        tc[used] = {ra,rb};
    }
    for(int i=1;i <= n+m; i++) if(parent[i] == i) dfs(0, i);
    lcainit(n+m);
    //printf("\n");

    //for(int i = 1; i <= n + m; i++) printf("%d ", parent[i]);
    //printf("\n");
    //for(int i = 1; i <= n + m; i++) printf("%d ", depth[i]);
    //printf("\n");
    int Q; scanf("%d", &Q);
    while(Q--)
    {
        int a,b; scanf("%d %d", &a,&b);
        int L = LCA(a,b);
        //printf("L : %d\n", L);
        if(L == -1) printf("-1\n");
        else printf("%d %d\n", weight[L], snn[L]);
    }
}

참고한 사이트
(1) 크루스칼의 공 :  https://rebro.kr/149
(2) https://justicehui.github.io/hard-algorithm/2020/02/24/pbs/