This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int n,m;
int q;
set<iii> AdjList[100001];
ii Q[100001];
int Q_res[100001];
int res = -1;
void bfs(int t)
{
queue<ii> CurrList;
CurrList.push(ii(n,t));
//cerr << "cur t: " << t << '\n';
while(!CurrList.empty())
{
int u = CurrList.front().first;
int tt = CurrList.front().second;
//cerr << u << '\n';
CurrList.pop();
set<iii>::iterator z1;
for (z1 = AdjList[u].begin();z1 != AdjList[u].end();z1++)
{
int cur_t = (*z1).first;
//cerr << cur_t << '\n';
if (cur_t <= tt)
{
int v = (*z1).second.first;
int w = (*z1).second.second;
//cerr << v << ' ' << w << '\n';
if (v == 1)
res = max(res,w);
else
CurrList.push(ii(v,w));
}
else
break;
}
AdjList[u].erase(AdjList[u].begin(),z1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int u,v,a,b;
cin >> u >> v >> a >> b;
AdjList[v].insert(iii(b,ii(u,a)));
}
cin >> q;
for (int i=1;i<=q;i++)
{
cin >> Q[i].first;
Q[i].second = i;
}
sort(Q+1,Q+1+q);
for (int i=1;i<=q;i++)
{
int cur_t = Q[i].first;
int id = Q[i].second;
bfs(cur_t);
Q_res[id] = res;
}
for (int i=1;i<=q;i++)
cout << Q_res[i] << '\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... |