Submission #1244801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244801		tvgk	버스 (JOI14_bus)	C++20	0 / 100	209 ms	37380 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];
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])
    {
        val[j].resize(w[j].size());
        sort(w[j].begin(), w[j].end(), cmp);
        vis[j] = 1;
    }

    while (ctr[j] < w[j].size())
    {
        int id = w[j][ctr[j]].se;
        int mem = ctr[j];
        ctr[j]++;
        val[j][mem] = DFS(v[id], en[id]);
    }

    if (vis[j] == 1)
    {
        for (int i = w[j].size() - 2; i >= 0; i--)
            val[j][i] = min(val[j][i], val[j][i + 1]);
        vis[j] = 2;
    }

    int tmp = lower_bound(w[j].begin(), w[j].end(), ii(t, 0)) - w[j].begin();
    if (tmp >= val[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: 0 / 20
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 50