oj.uz

Submission #8364

# Submission time Handle Problem Language Result Execution time Memory
8364 2014-09-13T14:24:53 Z gs14004 버스 (JOI14_bus) C++
35 / 100
 240 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
20.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 Correct 0 ms 5896 KB Output is correct
10 Correct 0 ms 5896 KB Output is correct
11 Correct 0 ms 5896 KB Output is correct
12 Correct 0 ms 5896 KB Output is correct
13 Correct 4 ms 5896 KB Output is correct
14 Correct 4 ms 5896 KB Output is correct

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 11836 KB Output is correct
2 Correct 200 ms 11836 KB Output is correct
3 Correct 200 ms 11836 KB Output is correct
4 Correct 204 ms 11836 KB Output is correct
5 Correct 208 ms 11836 KB Output is correct
6 Correct 216 ms 11852 KB Output is correct
7 Correct 184 ms 11724 KB Output is correct
8 Correct 184 ms 11732 KB Output is correct
9 Correct 204 ms 11968 KB Output is correct
10 Correct 168 ms 13568 KB Output is correct
11 Correct 168 ms 12380 KB Output is correct
12 Correct 172 ms 14712 KB Output is correct
13 Correct 192 ms 14712 KB Output is correct
14 Correct 156 ms 13572 KB Output is correct
15 Correct 172 ms 12980 KB Output is correct
16 Correct 56 ms 8932 KB Output is correct
17 Correct 44 ms 8932 KB Output is correct

Subtask #4
0.0 / 50.0

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