글 읽기 - 혹시 이문제 예외가 있나요?

smu201111192 7년 전 1

쿼리 전체를 바이너리 서치해주는

패러럴 바이너리서치로 접근해서 풀어봤는데

wa받앗습니다. 같은정점도 처리해줬고...

혹시 예외가처리 해줄게 있나요?

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX=111111;
vector<int> query[MAX];
struct edge{
    int u,v,cost;
    bool operator <(const edge e)const{
        return cost<e.cost;
    }
}e[MAX];
int parent[MAX],testCase,n,m,q,low[MAX],high[MAX],from[MAX],to[MAX],ans[MAX],sz[MAX]={0,},ansSz[MAX];
int edgeN;
void reset(){
    for(int i=0;i<=MAX-1;i++)parent[i]=i;
    for(int i=0;i<MAX;i++)query[i].clear();
    for(int i=0;i<=MAX-1;i++)sz[i]=1;
}
int find(int u){
    if(u==parent[u])return u;
    return parent[u]=find(parent[u]);
}
void mrg(int u,int v){
    u=find(u),v=find(v);
    if(u==v)return;
    parent[u]=v;
    sz[v]+=sz[u];
}
int main(){
    memset(ans,0,sizeof(ans));
    scanf("%d %d",&n,&m);
    edgeN=m;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].cost);
    }
    sort(e+1,e+m+1);
    scanf("%d",&q);
    reset();
    for(int i=1;i<=q;i++){
        cin>>from[i]>>to[i];
        low[i]=1,high[i]=m;
    }
    for(int i=0;i<=MAX-1;i++)ans[i]=1e9;
    while(true){
        bool good=false;
        reset();
        for(int i=1;i<=q;i++){
            if(low[i]<=high[i]){
                query[(low[i]+high[i])/2].push_back(i);
                good=true;
            }
        }
        if(!good)break;
        for(int i=1;i<=m;i++){
            mrg(e[i].u,e[i].v);
            for(int j=0;j<query[i].size();j++){
                int idx=query[i][j];
                int f=find(from[idx]);
                int t=find(to[idx]);
                if(f==t){
                    high[idx]=i-1;
                    if(ans[i]>e[i].cost){
                        ansSz[idx]=sz[t];
                        ans[idx]=e[i].cost;
                    }
                }
                else{
                    low[idx]=i+1;
                }
                
            }
        }
    }
    for(int i=1;i<=q;i++){
        if(from[i]==to[i])
            printf("%d %d\n",0,1);
       else printf("%d %d\n",ans[i],ansSz[i]);
    }
    
    
    return 0;
}

cokcjswo 7년 전 2

이번이 parallel binary search 푸는게 처음인데, 이해하기 쉬운 코드 공유해주셔서 풀었습니다. 감사합니다 ^^

smu201111192 7년 전 2

도움이 되셧다니 ㅎ 기뻐요 ><

sgc109 7년 전 0

ㅋㅋㅋㅋ 훈훈하네요 ㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

혹시 이문제 예외가 있나요?

smu201111192 7년 전 1

cokcjswo 7년 전 2

smu201111192 7년 전 2

sgc109 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말