Submission #31055

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

dd

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

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

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

int N,sy,fx;
Obstacle A[100000];
int Seg[9000005];
vector<int> adj[100005];
map<pair<int,int>,int> M;
set<int> S;
int fit;
priority_queue<State,vector<State> > pq;

int dijk(){
    pq.push(State(0,sy,0));
    while(!pq.empty()){
        State ns = pq.top();
        pq.pop();
        if(ns.n == 0){
            if(adj[0][0] == N+1){
                pq.push(State(adj[0][0],sy,(long long)fx));
                continue;
            }
            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){
                S.insert(ns.ny);
                fit = ns.c;
            }
            else{
                if(ns.c > fit) continue;
                else{
                    S.insert(ns.ny);
                }
            }
            continue;
        }
        if(M.find({ns.n,ns.ny}) != M.end()) continue;
        M[{ns.n,ns.ny}] = 1;
        if(ns.ny == A[ns.n-1].yl){
            int togo = adj[ns.n][0],toy = ns.ny;
            if(M.find({togo,toy}) != M.end()) continue;
            if(togo == N+1){
                pq.push(State(togo,toy,ns.c + (long long)fx - (long long)A[ns.n-1].x));
            }
            else pq.push(State(togo,toy,ns.c + (long long)A[togo-1].x - (long long)A[ns.n-1].x));
        }
        else if(ns.ny == A[ns.n-1].yh){
            int togo = adj[ns.n][1],toy = ns.ny;
            if(M.find({togo,toy}) != M.end()) continue;
            if(togo == N+1){
                pq.push(State(togo,toy,ns.c + (long long)fx - (long long)A[ns.n-1].x));
            }
            else pq.push(State(togo,toy,ns.c + (long long)A[togo-1].x - (long long)A[ns.n-1].x));
        }
        else{
            if(M.find({ns.n,A[ns.n-1].yl}) == M.end()){
                pq.push(State(ns.n,A[ns.n-1].yl,ns.c + (long long)ns.ny - (long long)A[ns.n-1].yl));
            }
            if(M.find({ns.n,A[ns.n-1].yh}) == M.end()){
                pq.push(State(ns.n,A[ns.n-1].yh,ns.c - (long long)ns.ny + (long long)A[ns.n-1].yh));
            }
        }
    }
}

int init(){
    int m = 0,p = 1;
    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);
        m = max(m,A[i].yh);
    }
    sort(A,A+N);
    while(p<=m) p*=2;
    for(int i=1;i<=p*2;i++) Seg[i] = N+1;
    int l,r,t;
    for(int i=N-1;i>=0;i--){
        t = INF;
        l = p+A[i].yl;
        while(l>=1){
            t = min(t,Seg[l]);
            l/=2;
        }
        adj[i+1].push_back(t);
        t = INF;
        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 = INF;
    l = p+sy;
    while(l>=1){
        t = min(t,Seg[l]);
        l/=2;
    }
    adj[0].push_back(t);
}

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

Compilation message (stderr)

dd.cpp: In function 'int dijk()':
dd.cpp:94:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
dd.cpp: In function 'int init()':
dd.cpp:145:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
dd.cpp: In function 'int main()':
dd.cpp:150:34: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::set<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n%d ",fit,S.size());
                                  ^
dd.cpp: In function 'int init()':
dd.cpp:98:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
                   ^
dd.cpp:99: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:101: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