#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 100005;
const int MAXV = 1000005;
int n,m,id = 0;
map<pair<int,int>,int> dict;
pair<int,int> cv[MAXV];
vector<int> adj[MAXV];
vector<int> node[MAXV];
struct edge{
int u,v,st,ed;
void read(){
cin>>u>>v>>st>>ed;
}
}e[MAXV];
int dp[MAXV];
void addEdge(int u,int v){
adj[v].push_back(u);
}
//n에 도착할 수 있는 가장 늦은 시점을 구하자.
int main(){
freopen("/Users/gangseong-yong/Downloads/2014-sp-d1-data/bus/in/04-15.txt","r",stdin);
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++){
//e[i].read();
cin >> e[i].u >> e[i].v >> e[i].st >> e[i].ed;
dict[{e[i].u,e[i].st}];
dict[{e[i].v,e[i].ed}];
node[e[i].u].push_back(e[i].st);
node[e[i].v].push_back(e[i].ed);
}
for(int i = 1; i <= n; i++) {
sort(node[i].begin(),node[i].end());
node[i].erase(unique(node[i].begin(),node[i].end()),node[i].end());
}
vector<pair<int,int> > ord;
for(auto it = dict.begin(); it!= dict.end(); it++){
it->second = ++id;
cv[id] = it->first;
ord.push_back({it->first.second,id});
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < (int)node[i].size() - 1; j++){
int tu = node[i][j];
int tv = node[i][j+1];
addEdge(dict[make_pair(i,tu)],dict[make_pair(i,tv)]);
}
}
for(int i = 1; i <= m; i++){
int u = e[i].u; int v = e[i].v;
int st = e[i].st; int ed = e[i].ed;
addEdge(dict[{u,st}],dict[{v,ed}]);
}
sort(ord.begin(),ord.end());
reverse(ord.begin(),ord.end());
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i = 0; i<ord.size();i++){
int x = ord[i].second;
int tm = ord[i].first;
int pv = cv[x].first;
if(pv == n)
dp[x] = tm;
for(auto y:adj[x])
dp[y] = min(dp[y],dp[x]);
}
int Q; cin>> Q;
for(int i = 1; i <= Q; i++){
int tm; cin >> tm;
if(node[1].size() == 0) {
cout<<-1; continue;
}
int lo = 0; int hi = node[1].size() - 1;
int ret = -1;
while(lo <= hi){
int mid = (lo + hi)/2;
int t = node[1][mid];
//요시간에 출발하면 언제 도착혀?
int v = dict[{1,t}];
if(dp[v] <= tm){
ret = max(ret,t);
lo = mid + 1;
}
else hi = mid - 1;
}
cout<<ret<<"\n";
}
return 0;
}
Compilation message
bus.cpp: In function 'int main()':
bus.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<ord.size();i++){
^
bus.cpp:40:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("/Users/gangseong-yong/Downloads/2014-sp-d1-data/bus/in/04-15.txt","r",stdin);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
95 ms |
94584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
95 ms |
94800 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
118 ms |
94904 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
94 ms |
94904 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
