| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 16301 |
2015-08-20T03:07:49 Z |
eaststar |
버스 (JOI14_bus) |
C++14 |
|
1000 ms |
19792 KB |
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
struct data{
int a,b,x,y;
bool operator<(const data&r)const{
if(a==r.a)return x>r.x;
return a<r.a;
}
}a[300010];
struct ans{
int s,e;
bool operator<(const ans&r)const{
if(e==r.e)return s>r.s;
return e>r.e;
}
}b[300010],t;
map<int,int> mn[100010];
int st[100010],cnt,n,m;
int f(int p,int t){
int i,m=1e8;
if(p==n)return t;
if(mn[p][t])return mn[p][t];
for(i=st[p];a[i].a==p&&a[i].x>=t;++i)m=min(m,f(a[i].b,a[i].y));
return mn[p][t]=m;
}
int main(){
int i,q;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)scanf("%d%d%d%d",&a[i].a,&a[i].b,&a[i].x,&a[i].y);
sort(a+1,a+m+1);
for(i=1;i<=m;++i)if(a[i].a!=a[i-1].a)st[a[i].a]=i;
a[0].x=-1;
for(i=1;a[i].a==1;++i)if(a[i].x!=a[i-1].x)b[cnt].s=a[i].x,b[cnt++].e=f(1,a[i].x);
sort(b,b+cnt);
scanf("%d",&q);
t.s=1e9;
for(;q--;){
scanf("%d",&t.e);
i=lower_bound(b,b+cnt,t)-b;
printf("%d\n",i==cnt?-1:b[i].s);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
13328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
13328 KB |
Output is correct |
| 3 |
Correct |
0 ms |
13328 KB |
Output is correct |
| 4 |
Correct |
3 ms |
13328 KB |
Output is correct |
| 5 |
Correct |
0 ms |
13328 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13328 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13328 KB |
Output is correct |
| 8 |
Correct |
0 ms |
13328 KB |
Output is correct |
| 9 |
Correct |
3 ms |
13328 KB |
Output is correct |
| 10 |
Correct |
0 ms |
13328 KB |
Output is correct |
| 11 |
Correct |
3 ms |
13328 KB |
Output is correct |
| 12 |
Correct |
4 ms |
13328 KB |
Output is correct |
| 13 |
Correct |
3 ms |
13356 KB |
Output is correct |
| 14 |
Correct |
15 ms |
13328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
13328 KB |
Output is correct |
| 2 |
Correct |
38 ms |
13328 KB |
Output is correct |
| 3 |
Correct |
22 ms |
13328 KB |
Output is correct |
| 4 |
Correct |
6 ms |
13328 KB |
Output is correct |
| 5 |
Correct |
0 ms |
13328 KB |
Output is correct |
| 6 |
Correct |
6 ms |
13328 KB |
Output is correct |
| 7 |
Correct |
29 ms |
13328 KB |
Output is correct |
| 8 |
Correct |
3 ms |
13328 KB |
Output is correct |
| 9 |
Correct |
25 ms |
13328 KB |
Output is correct |
| 10 |
Correct |
49 ms |
13328 KB |
Output is correct |
| 11 |
Correct |
19 ms |
13356 KB |
Output is correct |
| 12 |
Correct |
56 ms |
13328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
257 ms |
13328 KB |
Output is correct |
| 2 |
Correct |
186 ms |
13328 KB |
Output is correct |
| 3 |
Correct |
186 ms |
13328 KB |
Output is correct |
| 4 |
Correct |
86 ms |
13328 KB |
Output is correct |
| 5 |
Correct |
75 ms |
13328 KB |
Output is correct |
| 6 |
Correct |
335 ms |
13592 KB |
Output is correct |
| 7 |
Correct |
410 ms |
15704 KB |
Output is correct |
| 8 |
Execution timed out |
1000 ms |
14512 KB |
Program timed out |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
13328 KB |
Output is correct |
| 2 |
Correct |
212 ms |
13328 KB |
Output is correct |
| 3 |
Correct |
223 ms |
13328 KB |
Output is correct |
| 4 |
Correct |
257 ms |
13328 KB |
Output is correct |
| 5 |
Correct |
207 ms |
13328 KB |
Output is correct |
| 6 |
Correct |
313 ms |
13592 KB |
Output is correct |
| 7 |
Correct |
423 ms |
15704 KB |
Output is correct |
| 8 |
Correct |
321 ms |
13592 KB |
Output is correct |
| 9 |
Correct |
303 ms |
13592 KB |
Output is correct |
| 10 |
Execution timed out |
1000 ms |
19792 KB |
Program timed out |
| 11 |
Halted |
0 ms |
0 KB |
- |
