oj.uz

Submission #8360

# Submission time Handle Problem Language Result Execution time Memory
8360 2014-09-13T08:56:03 Z gs14004 버스 (JOI14_bus) C++
35 / 100
 1000 ms 14592 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()(const ln& a, const ln& b){return a.s < b.s;}};

int n,m,q;
priority_queue<ln,vector<ln>,cmp> pq;
void process(int lim, int save){
    int v[100005] = {};
    // 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] = 1;
        if(pos == 1){
            res[save] = t.s;
            return;
        }
        pq.pop();
        while (!graph[pos].empty()) {
            ln u = graph[pos].top();
            if(u.e > t.s) break;
            graph[pos].pop();
            if(v[u.pos]) 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 5772 KB Output is correct
2 Correct 0 ms 5776 KB Output is correct
3 Correct 0 ms 5776 KB Output is correct
4 Correct 0 ms 5772 KB Output is correct
5 Correct 0 ms 5772 KB Output is correct
6 Correct 0 ms 5776 KB Output is correct
7 Correct 0 ms 5772 KB Output is correct
8 Correct 0 ms 5772 KB Output is correct
9 Correct 0 ms 5772 KB Output is correct
10 Correct 0 ms 5772 KB Output is correct
11 Correct 4 ms 5768 KB Output is correct
12 Correct 0 ms 5772 KB Output is correct
13 Correct 4 ms 5772 KB Output is correct
14 Correct 0 ms 5772 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5772 KB Output is correct
2 Execution timed out 1000 ms 5772 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 11716 KB Output is correct
2 Correct 212 ms 11716 KB Output is correct
3 Correct 208 ms 11716 KB Output is correct
4 Correct 212 ms 11712 KB Output is correct
5 Correct 208 ms 11716 KB Output is correct
6 Correct 220 ms 11728 KB Output is correct
7 Correct 200 ms 11600 KB Output is correct
8 Correct 200 ms 11612 KB Output is correct
9 Correct 228 ms 11848 KB Output is correct
10 Correct 164 ms 13440 KB Output is correct
11 Correct 176 ms 12260 KB Output is correct
12 Correct 188 ms 14592 KB Output is correct
13 Correct 176 ms 14588 KB Output is correct
14 Correct 184 ms 13452 KB Output is correct
15 Correct 172 ms 12856 KB Output is correct
16 Correct 76 ms 8808 KB Output is correct
17 Correct 60 ms 8808 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 11708 KB Program timed out
2 Halted 0 ms 0 KB -