Submission #1244862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244862		tvgk	버스 (JOI14_bus)	C++20	100 / 100	131 ms	30788 KiB

bus

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 3e5 + 7, inf = 1e9 + 7;

int n, m, v[mxN], en[mxN], vis[mxN], ctr[mxN], mn[mxN];
vector<int> val[mxN];
vector<ii> w[mxN];

bool cmp(ii u, ii v)
{
    return u.fi < v.fi;
}

int DFS(int j, int t)
{
    if (j == n)
        return t;

    if (!vis[j])
    {
        mn[j] = inf;
        val[j].resize(w[j].size());
        sort(w[j].begin(), w[j].end(), cmp);
        ctr[j] = w[j].size() - 1;
        vis[j] = 1;
    }

    while (ctr[j] >= 0 && w[j][ctr[j]].fi >= t)
    {
        int id = w[j][ctr[j]].se;
        mn[j] = min(mn[j], DFS(v[id], en[id]));
        val[j][ctr[j]] = mn[j];
        ctr[j]--;
    }

    int tmp = lower_bound(w[j].begin(), w[j].end(), ii(t, 0)) - w[j].begin();
    if (tmp >= w[j].size())
        return inf;
    return val[j][tmp];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int stt, u;
        cin >> u >> v[i] >> stt >> en[i];
        w[u].push_back({stt, i});
    }
    DFS(1, 0);

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int tmp;
        cin >> tmp;
        tmp = upper_bound(val[1].begin(), val[1].end(), tmp) - val[1].begin() - 1;

        if (tmp < 0)
            cout << -1 << '\n';
        else
            cout << w[1][tmp].fi << '\n';
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50