# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|
1244862 | | tvgk | 버스 (JOI14_bus) | C++20 | | 131 ms | 30788 KiB |
#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';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |