oj.uz

답안 #16301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16301 2015-08-20T03:07:49 Z eaststar 버스 (JOI14_bus) C++14
35 / 100
 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;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 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

Subtask #3
0.0 / 15.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 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 -