oj.uz

Submission #56872

# Submission time Handle Problem Language Result Execution time Memory
56872 2018-07-13T01:41:16 Z Jeez 버스 (JOI14_bus) C++14
35 / 100
 777 ms 146296 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int MAX_N = 100 * 1000 + 9;
const ll INF = 1e9;

struct Edge {
    int v;
    ll in, out;
    Edge(){};
    Edge(int b, ll c, ll d) : v(b), in(c), out(d) {};
};
int n, m, q;
ll latest[MAX_N];
vector<Edge> g[MAX_N];

void read(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, in, out;
        cin >> u >> v >> in >> out;
        g[v].push_back(Edge(u, out, in));
    }
}

void dijk(ll curT){
    priority_queue<pair<ll, int> > pq;
    fill_n(latest, n + 1, -INF);
    latest[n] = curT;
    pq.push(make_pair(curT, n));
    while(!pq.empty()){
        ll latestu = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if(latestu != latest[u])
            continue;

        for(int i = 0, L = g[u].size(); i < L; i++){
            int v = g[u][i].v;
            ll in = g[u][i].in;
            ll out = g[u][i].out;
            if(in > latest[u])
                continue;

            if(latest[v] < out){
                latest[v] = out;
                pq.push(make_pair(latest[v], v));
            }
        }
    }

    cout << max(latest[1], -1LL) << '\n';
}

void solve(){
    cin >> q;
    if(q == 1){
        ll curT;   cin >> curT;
        dijk(curT);
    }
}

int main()
{
    //freopen("in.inp", "r", stdin);
    read();
    solve();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 6 ms 2932 KB Output is correct
3 Correct 6 ms 2932 KB Output is correct
4 Correct 6 ms 2932 KB Output is correct
5 Correct 4 ms 2932 KB Output is correct
6 Correct 4 ms 3028 KB Output is correct
7 Correct 4 ms 3028 KB Output is correct
8 Correct 4 ms 3028 KB Output is correct
9 Correct 4 ms 3028 KB Output is correct
10 Correct 7 ms 3080 KB Output is correct
11 Correct 7 ms 3100 KB Output is correct
12 Correct 7 ms 3104 KB Output is correct
13 Correct 9 ms 3352 KB Output is correct
14 Correct 9 ms 3352 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3352 KB Output is correct
2 Incorrect 6 ms 3352 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 620 ms 23516 KB Output is correct
2 Correct 777 ms 32212 KB Output is correct
3 Correct 726 ms 40776 KB Output is correct
4 Correct 714 ms 49476 KB Output is correct
5 Correct 700 ms 57972 KB Output is correct
6 Correct 700 ms 66760 KB Output is correct
7 Correct 630 ms 74912 KB Output is correct
8 Correct 661 ms 83148 KB Output is correct
9 Correct 709 ms 92008 KB Output is correct
10 Correct 569 ms 99580 KB Output is correct
11 Correct 539 ms 106868 KB Output is correct
12 Correct 505 ms 114156 KB Output is correct
13 Correct 534 ms 121664 KB Output is correct
14 Correct 502 ms 129332 KB Output is correct
15 Correct 637 ms 136556 KB Output is correct
16 Correct 244 ms 136556 KB Output is correct
17 Correct 194 ms 136556 KB Output is correct

Subtask #4
0 / 50.0

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