# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
43209 |
2018-03-10T22:18:10 Z |
smu201111192 |
버스 (JOI14_bus) |
C++14 |
|
302 ms |
62992 KB |
#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 = 500005;
int n,m,id = 0;
map<pair<int,int>,int> dict;
pair<int,int> cv[MAXV];
vector<int> adj[MAXV];
vector<int> node[MAXN];
struct edge{
int u,v,st,ed;
void read(){cin>>u>>v>>st>>ed;}
}e[MAXN];
int dp[MAXV];
void addEdge(int u,int v){
adj[u].push_back(v);
}
int go(int cur){
int v = cv[cur].first;
int tm = cv[cur].second;
if(v == n) return tm;
int &ret = dp[cur];
if(ret != -1) return ret;
ret = 2e9;
for(auto x : adj[cur]){
ret = min(ret,go(x));
}
return ret;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
node[1].push_back(0);
for(int i = 1; i <= m; i++){
e[i].read();
dict[make_pair(e[i].u,e[i].st)];
dict[make_pair(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());
}
dict[make_pair(1,0)];
for(auto it = dict.begin(); it!= dict.end(); it++){
it->second = ++id;
cv[id] = it->first;
}
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;
adj[dict[make_pair(u,st)]].push_back(dict[make_pair(v,ed)]);
}
assert(id<MAXV);
memset(dp,-1,sizeof(dp));
int q; cin >> q;
for(int i = 1;i <= q; i++){
int goal; cin >> goal;
int low = 0;
int high = node[1].size()-1;
int ans = -1;
while(low <= high){
int mid = (low+high)/2;
int id = dict[make_pair(1,node[1][mid])];
if(go(id) <= goal){
ans = max(ans,node[1][mid]);
low = mid + 1;
}
else high = mid - 1;
}
cout<<ans<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16508 KB |
Output is correct |
2 |
Correct |
15 ms |
16608 KB |
Output is correct |
3 |
Correct |
19 ms |
16680 KB |
Output is correct |
4 |
Correct |
15 ms |
16680 KB |
Output is correct |
5 |
Correct |
16 ms |
16680 KB |
Output is correct |
6 |
Correct |
15 ms |
16716 KB |
Output is correct |
7 |
Correct |
16 ms |
16716 KB |
Output is correct |
8 |
Correct |
15 ms |
16716 KB |
Output is correct |
9 |
Correct |
15 ms |
16716 KB |
Output is correct |
10 |
Correct |
15 ms |
16840 KB |
Output is correct |
11 |
Correct |
18 ms |
17132 KB |
Output is correct |
12 |
Correct |
18 ms |
17132 KB |
Output is correct |
13 |
Correct |
18 ms |
17260 KB |
Output is correct |
14 |
Correct |
19 ms |
17260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
17260 KB |
Output is correct |
2 |
Correct |
55 ms |
17516 KB |
Output is correct |
3 |
Correct |
54 ms |
17620 KB |
Output is correct |
4 |
Correct |
20 ms |
17620 KB |
Output is correct |
5 |
Correct |
23 ms |
17620 KB |
Output is correct |
6 |
Correct |
19 ms |
17620 KB |
Output is correct |
7 |
Correct |
44 ms |
17620 KB |
Output is correct |
8 |
Correct |
15 ms |
17620 KB |
Output is correct |
9 |
Correct |
36 ms |
17620 KB |
Output is correct |
10 |
Correct |
68 ms |
17964 KB |
Output is correct |
11 |
Correct |
39 ms |
17964 KB |
Output is correct |
12 |
Correct |
110 ms |
18200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
302 ms |
62864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
277 ms |
62992 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |