제출 #8369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8369		gs14004	버스 (JOI14_bus)	C++98	35 / 100	252 ms	14712 KiB

bus

#include <cstdio>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> pi;

int res[100005];
pi query[100005];

struct ln{int pos,s,e;};
priority_queue<ln> graph[100005];
bool operator<(ln a, ln b){return a.e > b.e;}
struct cmp{bool operator()(ln a, ln b){return a.s < b.s;}};

int n,m,q;
priority_queue<ln,vector<ln>,cmp> pq;

int v[100005];
void process(int lim, int save){
    // e small guy out
    int pos = n;
    while (!graph[pos].empty()) {
        ln t = graph[pos].top();
        if(t.e > lim) break;
        pq.push(t);
        graph[pos].pop();
    }
    while (!pq.empty()) {
        // s big guy out
        ln t = pq.top();
        pos = t.pos;
        v[pos] = t.s;
        pq.pop();
        if(pos == 1){
            res[save] = t.s;
            return;
        }
        while (!graph[pos].empty()) {
            ln u = graph[pos].top();
            if(u.e > t.s) break;
            graph[pos].pop();
            if(v[u.pos] > u.s) continue;
            pq.push(u);
        }
    }
    if(save) res[save] = max(-1,res[save-1]);
    else res[save] = -1;
}

int main(){
    int p,q,r,s;
    scanf("%d %d",&n,&m);
    for (int i=0; i<m; i++) {
        scanf("%d %d %d %d",&p,&q,&r,&s);
        graph[q].push({ p,r,s});
        // 2 -> 1 10 25
    }
    scanf("%d",&q);
    for (int i=0; i<q; i++) {
        scanf("%d",&query[i].first);
        query[i].second = i;
    }
    sort(query,query+q);
    for (int i=0; i<q; i++) {
        process(query[i].first,query[i].second);
    }
    for (int i=0; i<q; i++) {
        printf("%d\n",res[i]);
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 50