Submission #31057

#	Time	Username	Problem	Language	Result	Execution time	Memory
31057		asdjke	장애물 경기 (KOI16_dd)	C++14	0 / 100	2000 ms	29760 KiB

dd

#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;

class Obs{
public:
    int x,yl,yh;
    bool operator < (const Obs& b) const{
        if(b.x > x) return true;
        return false;
    }
};

class State{
public:
    int n,y;
    long long c;
    State(int n,int y,long long c){
        this->n = n;
        this->y = y;
        this->c = c;
    }
    bool operator < (const State& b) const{
        if(b.c < c) return true;
        return false;
    }
};

int N,sy,fx;
Obs A[100000];
vector<int> adj[100005];
set<int> v[100005],S;
long long fit;
int Seg[5000005];

int input(){
    scanf("%d",&N);
    scanf("%d%d",&sy,&fx);
    for(int i=0;i<N;i++){
        scanf("%d%d%d",&A[i].x,&A[i].yl,&A[i].yh);
    }
    sort(A,A+N);
    return 0;
}

int init(){
    int m = 0,p = 1;
    for(int i=0;i<N;i++) if(m < A[i].yh) m = A[i].yh;
    while(p <= m) p*=2;
    int t,l,r;
    for(int i=1;i<=p*2;i++) Seg[i] = N+1;
    for(int i=N-1;i>=0;i--){
        t = N+1;
        l = p+A[i].yl;
        while(l>=1){
            t = min(t,Seg[l]);
            l/=2;
        }
        adj[i+1].push_back(t);
        t = N+1;
        l = p+A[i].yh;
        while(l>=1){
            t = min(t,Seg[l]);
            l/=2;
        }
        adj[i+1].push_back(t);
        l = p+A[i].yl;
        r = p+A[i].yh;
        while(l<=r){
            if(l%2==1){
                Seg[l] = i+1;
                l++;
            }
            if(r%2==0){
                Seg[r] = i+1;
                r--;
            }
            l/=2;
            r/=2;
        }
    }
    t = N+1;
    l = p+sy;
    while(l>=1){
        t = min(t,Seg[l]);
        l/=2;
    }
    adj[0].push_back(t);
    return 0;
}

int dijk(){
    priority_queue<State,vector<State> > pq;
    pq.push(State(0,sy,0));
    while(!pq.empty()){
        State ns = pq.top();
        if(fit!=0 && ns.c > fit) break;
        pq.pop();
        if(ns.n == 0){
            if(adj[0][0] == N+1){
                pq.push(State(adj[0][0],sy,(long long)fx));
            }
            else{
                pq.push(State(adj[0][0],sy,(long long)A[adj[0][0]-1].x));
            }
            continue;
        }
        if(ns.n == N+1){
            if(S.size() == 0){
                fit = ns.c;
                S.insert(ns.y);
            }
            else{
                if(fit == ns.c){
                    S.insert(ns.y);
                }
            }
            continue;
        }
        if(v[ns.n].find(ns.y) != v[ns.n].end()) continue;
        v[ns.n].insert(ns.y);
        if(ns.y == A[ns.n-1].yl){
            int togo = adj[ns.n][0];
            long long toc;
            if(togo == N+1) toc = ns.c + (long long)fx - (long long)A[ns.n-1].x;
            else toc = ns.c + (long long)A[togo-1].x - (long long)A[ns.n-1].x;
            if(v[togo].find(ns.y) != v[togo].end()) continue;
            pq.push(State(togo,ns.y,toc));
        }
        else if(ns.y == A[ns.n-1].yh){
            int togo = adj[ns.n][1];
            long long toc;
            if(togo == N+1) toc = ns.c + (long long)fx - (long long)A[ns.n-1].x;
            else toc = ns.c + (long long)A[togo-1].x - (long long)A[ns.n-1].x;
            if(v[togo].find(ns.y) != v[togo].end()) continue;
            pq.push(State(togo,ns.y,toc));
        }
        else{
            int togo = adj[ns.n][0];
            long long toc;
            toc = ns.c + (long long)ns.y - (long long)A[ns.n-1].yl;
            if(togo == N+1) toc += (long long)fx - (long long)A[ns.n-1].x;
            else toc += (long long)A[togo-1].x - (long long)A[ns.n-1].x;
            if(v[togo].find(A[ns.n-1].yl) == v[togo].end()){
                pq.push(State(togo,A[ns.n-1].yl,toc));
            }
            togo = adj[ns.n][1];
            toc = ns.c - (long long)ns.y + (long long)A[ns.n-1].yh;
            if(togo == N+1) toc += (long long)fx - (long long)A[ns.n-1].x;
            else toc += (long long)A[togo-1].x - (long long)A[ns.n-1].x;
            if(v[togo].find(A[ns.n-1].yh) == v[togo].end()){
                pq.push(State(togo,A[ns.n-1].yh,toc));
            }
        }
    }
}

int main(){
    input();
    init();
    dijk();
    printf("%lld\n",fit);
    printf("%d ",S.size());
    for(auto i : S) printf("%d ",i);
}

Compilation message (stderr)

dd.cpp: In function 'int dijk()':
dd.cpp:157:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
dd.cpp: In function 'int main()':
dd.cpp:164:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d ",S.size());
                          ^
dd.cpp: In function 'int input()':
dd.cpp:38:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
                   ^
dd.cpp:39:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&sy,&fx);
                          ^
dd.cpp:41:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&A[i].x,&A[i].yl,&A[i].yh);
                                                  ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 36