oj.uz

Submission #56875

# Submission time Handle Problem Language Result Execution time Memory
56875 2018-07-13T02:07:31 Z Jeez 버스 (JOI14_bus) C++14
100 / 100
 358 ms 25100 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;
int curIdx[MAX_N];
ll latest[MAX_N], ans[MAX_N];
vector<Edge> g[MAX_N];
pair<ll, int> queries[MAX_N];

bool cmp(Edge lhs, Edge rhs){
    return lhs.in < rhs.in;
}

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));
    }
}

ll dijk(ll curT){
    priority_queue<pair<ll, int> > pq;
    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 = curIdx[u], L = g[u].size(); i < L; i++, curIdx[u]++){
            int v = g[u][i].v;
            ll in = g[u][i].in;
            ll out = g[u][i].out;
            if(in > latest[u])
                break;

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

    return max(latest[1], -1LL);
}

void solve(){
    fill_n(latest, n + 1, -INF);
    for(int i = 1; i <= n; i++)
        sort(g[i].begin(), g[i].end(), cmp);

    cin >> q;
    if(q == 1){
        ll curT;   cin >> curT;
        cout << dijk(curT) << '\n';
    } else {
        for(int i = 0; i < q; i++){
            cin >> queries[i].first;
            queries[i].second = i;
        }

        sort(queries, queries + q);
        for(int i = 0; i < q; i++)
            ans[queries[i].second] = dijk(queries[i].first);

        for(int i = 0; i < q; i++)
            cout << ans[i] << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //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 2928 KB Output is correct
3 Correct 5 ms 2928 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 4 ms 3040 KB Output is correct
6 Correct 4 ms 3040 KB Output is correct
7 Correct 5 ms 3072 KB Output is correct
8 Correct 4 ms 3072 KB Output is correct
9 Correct 5 ms 3072 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct
11 Correct 6 ms 3276 KB Output is correct
12 Correct 7 ms 3276 KB Output is correct
13 Correct 7 ms 3276 KB Output is correct
14 Correct 6 ms 3284 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3284 KB Output is correct
2 Correct 45 ms 7268 KB Output is correct
3 Correct 55 ms 8084 KB Output is correct
4 Correct 14 ms 8084 KB Output is correct
5 Correct 10 ms 8084 KB Output is correct
6 Correct 8 ms 8084 KB Output is correct
7 Correct 42 ms 8360 KB Output is correct
8 Correct 5 ms 8360 KB Output is correct
9 Correct 40 ms 8672 KB Output is correct
10 Correct 44 ms 10168 KB Output is correct
11 Correct 43 ms 10168 KB Output is correct
12 Correct 56 ms 11696 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 21696 KB Output is correct
2 Correct 319 ms 21776 KB Output is correct
3 Correct 241 ms 22032 KB Output is correct
4 Correct 313 ms 22032 KB Output is correct
5 Correct 319 ms 22032 KB Output is correct
6 Correct 249 ms 22032 KB Output is correct
7 Correct 211 ms 22032 KB Output is correct
8 Correct 244 ms 22032 KB Output is correct
9 Correct 288 ms 22176 KB Output is correct
10 Correct 249 ms 22176 KB Output is correct
11 Correct 222 ms 22176 KB Output is correct
12 Correct 186 ms 22176 KB Output is correct
13 Correct 209 ms 22176 KB Output is correct
14 Correct 205 ms 22176 KB Output is correct
15 Correct 213 ms 22176 KB Output is correct
16 Correct 129 ms 22176 KB Output is correct
17 Correct 86 ms 22176 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 24948 KB Output is correct
2 Correct 348 ms 24948 KB Output is correct
3 Correct 271 ms 24992 KB Output is correct
4 Correct 358 ms 25100 KB Output is correct
5 Correct 276 ms 25100 KB Output is correct
6 Correct 295 ms 25100 KB Output is correct
7 Correct 264 ms 25100 KB Output is correct
8 Correct 285 ms 25100 KB Output is correct
9 Correct 326 ms 25100 KB Output is correct
10 Correct 245 ms 25100 KB Output is correct
11 Correct 276 ms 25100 KB Output is correct
12 Correct 238 ms 25100 KB Output is correct
13 Correct 265 ms 25100 KB Output is correct
14 Correct 242 ms 25100 KB Output is correct
15 Correct 271 ms 25100 KB Output is correct
16 Correct 179 ms 25100 KB Output is correct