알고리즘 고수님들 좀도와주세요~~

  • shinhj88
    shinhj88

    [체인점][http://www.acmicpc.net/problem/2472]
    제가요세 2010년도 정보올림파아드 고등부문제를 풀고있는데
    이 알고리즘이 1초에 안에 나올꺼라 생각되는데 풀리 지않아서 도움을 청합니다.

    문제를 간단하게 설명해 드리면 최대 10만개의 노드를가지고 한노드는 최대 5개의 간선을 가질수있고,임의의 노드에서 또다른 임의의 노드로 도달가능합니다. 그리고 3개의 임의의 노드(a,b,c)가 주어집니다. 주어진 3개의 노드에서 주언진 모든 노드까지 거리를 ak bk ck라 할때 임의의 노드 i ,j 에 대해 ai>aj bi>bj ci>cj 이 조건에 해당되는 노드를 찾아 내는 문제입니다.

    저는 주어진 임의의노드 3개에서 부터 모든 노드까지 거리를 우선순위 큐를 이용하여 구하고
    bk 를 기준으로 오름차순으로 정렬한후 index를 맵핑시킨고 ak기준으로 다시 정렬시킨다음에 구간트리를 이용하여 ak를 기준으로 정렬시킨 순으로 구간트리에 넣었습니다.
    구간트리에 넣을때 bk를 구간트리의 구간에 대한 인덱스로 넣어두고 ck를 키값으로 하는 구간트리를 만들었습니다.
    그래서 다음 ak수으로 정렬되 노드가 주어지면 앞서서 만들어진 구간트리(구간 1~bk-1) 에서 가장작은 키값을 찾아 ck와 비교하여 작으면 ai>aj bi>bj ci>cj 이조건에 해당되는 노드라고 체크하였습니다.
    그러나 이것이 시간초가가 계속 떠서 고생하고 있습니다.
    고수님들 도와주세요~~

    밑에는 제소스를 첨부합니다.

    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <numeric>
    #include <limits>
    #include <memory.h>
    #include <algorithm>
    #include <cstdlib>
    using namespace std;
    #define MAX_N 100001
    const long INF = numeric_limits<long>::max();
    int N;
    int store[3];
    bool check[MAX_N];
    vector<pair<long,int> > adj[MAX_N];
    typedef struct Candidate{
        long fromstore[3],newindx;
        int idx;
        Candidate(){
            for(int i=0;i<3;i++)
            {
                fromstore[i]=INF;
            }
    
        }   
    };
    int amountidx;
    long rangeMin[400100];
    Candidate data[MAX_N];
    void setBIT(int n)
    {
       memset(rangeMin,-1,sizeof(rangeMin));
    }
    long update(int index,long newValue,int node,int nodeleft,int noderight)
    {
        if(rangeMin[node]==-1)rangeMin[node]=INF;
        if(index<nodeleft||noderight<index)return rangeMin[node];
        if(nodeleft==noderight)
        {
            if(rangeMin[node]>newValue)rangeMin[node]=newValue;
            return rangeMin[node];
        }
        int mid=(nodeleft+noderight)/2;
        return rangeMin[node]=min(update(index,newValue,node*2,nodeleft,mid),update(index,newValue,node*2+1,mid+1,noderight));
    }
    long query(int left,int right,int node,int nodeleft,int noderight)
    {
        if(rangeMin[node]==-1)rangeMin[node]=INF;
        if(right<nodeleft||noderight<left)return INF;
        if(nodeleft==noderight)return rangeMin[node];
        int mid=(nodeleft+noderight)/2;
        return min(query(left,right,node*2,nodeleft,mid),query(left,right,node*2+1,mid+1,noderight));
    }
    void input()
    {
        scanf("%d",&N);
        for(int i=0;i<3;i++)
        {
            scanf("%d",&store[i]);
        }
        int m;
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            int a,b;
            long c;
            scanf("%d %d %ld",&a,&b,&c);
            adj[a].push_back(make_pair(c,b));
            adj[b].push_back(make_pair(c,a));
        }
    
    }
    void dijkstra(int src)
    {
        int u=store[src],v;
        priority_queue<pair<long ,int > >PQ;
        data[u].fromstore[src]=0;
        PQ.push(make_pair(0,u));
        while(!PQ.empty())
        {
            pair<long,int> PQT=PQ.top();
            PQ.pop();
            u=PQT.second;
            long cost=-PQT.first;
            if(data[u].fromstore[src]<cost)continue;
            data[u].idx=u;
            for(int i=0;i<adj[u].size();i++)
            {
                v=adj[u][i].second;
                long nextcost=cost+adj[u][i].first;
                if(nextcost<data[v].fromstore[src])
                {
                    data[v].fromstore[src]=nextcost;
                    PQ.push(make_pair(-nextcost,v));
                }
            }
        }
    }
    long cmp2(const Candidate &a,const Candidate &b)
    {
        return a.fromstore[1]<b.fromstore[1];
    }
    long cmp1(const Candidate &a,const Candidate &b)
    {
        return a.fromstore[0]<b.fromstore[0];
    }
    void mapping()
    {
        long idx=1;
        for(int i=1;i<N;i++)
        {
            if(data[i].fromstore[1]==data[i+1].fromstore[1])data[i].newindx=idx;
            else data[i].newindx=idx++;
        }
        data[N].newindx=idx;
        amountidx=idx;
    }
    void checkEstanblish()
    {
        long ret;
        setBIT(amountidx);
        for(int i=1;i<=N;i++)
        {
            ret=query(1,N,1,1,data[i].newindx-1);
            update(data[i].newindx,data[i].fromstore[2],1,1,N);
            if(ret<data[i].fromstore[2])check[data[i].idx]=true;        
        }
    }
    void ans()
    {
        int Q;
        scanf("%d",&Q);
        while(Q--)
        {
            int idx;
            scanf("%d",&idx);
            if(!check[idx])printf("YES\n");
            else printf("NO\n");
        }
    }
    int main()
    {
        input();
        for(int i=0;i<3;i++)dijkstra(i);
        sort(data+1,data+N+1,cmp2);
        mapping();
        sort(data+1,data+N+1,cmp1);
        checkEstanblish();
        ans();
        return 0;
    }
    


    10년 전
3개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    음..알고리즘적으론 맞는거같은데요 ㅠㅠ


    10년 전 link
  • 샥후
    샥후

    query 함수가 느립니다.


    10년 전 link
  • shinhj88
    shinhj88

    아~ 감사합니다.....


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.