oj.uz

Submission #8363

# Submission time Handle Problem Language Result Execution time Memory
8363 2014-09-13T14:24:27 Z gs14004 버스 (JOI14_bus) C++
0 / 100
 236 ms 14712 KB 
#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);
        }
    }
    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
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5896 KB Output is correct
2 Correct 0 ms 5896 KB Output is correct
3 Correct 0 ms 5896 KB Output is correct
4 Correct 0 ms 5896 KB Output is correct
5 Correct 0 ms 5896 KB Output is correct
6 Correct 0 ms 5896 KB Output is correct
7 Correct 0 ms 5896 KB Output is correct
8 Correct 0 ms 5896 KB Output is correct
9 Incorrect 0 ms 5896 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5896 KB Output is correct
2 Incorrect 36 ms 5896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 11836 KB Output is correct
2 Correct 204 ms 11836 KB Output is correct
3 Correct 212 ms 11836 KB Output is correct
4 Correct 196 ms 11836 KB Output is correct
5 Correct 184 ms 11836 KB Output is correct
6 Correct 192 ms 11852 KB Output is correct
7 Correct 180 ms 11724 KB Output is correct
8 Correct 204 ms 11732 KB Output is correct
9 Correct 200 ms 11968 KB Output is correct
10 Correct 164 ms 13568 KB Output is correct
11 Correct 160 ms 12380 KB Output is correct
12 Correct 172 ms 14712 KB Output is correct
13 Correct 164 ms 14712 KB Output is correct
14 Correct 188 ms 13572 KB Output is correct
15 Correct 156 ms 12980 KB Output is correct
16 Incorrect 68 ms 8932 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 11836 KB Output isn't correct
2 Halted 0 ms 0 KB -