Submission #113720

#TimeUsernameProblemLanguageResultExecution timeMemory
113720mbfibat버스 (JOI14_bus)C++14
100 / 100
525 ms35320 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...