Submission #56875

#	Time	Username	Problem	Language	Result	Execution time	Memory
56875		Jeez	버스 (JOI14_bus)	C++14	100 / 100	358 ms	25100 KiB

bus

#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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50