oj.uz

답안 #16300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16300 2015-08-20T01:38:10 Z eaststar 버스 (JOI14_bus) C++14
35 / 100
 1000 ms 8508 KB 
#include <stdio.h>
#include <algorithm>
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;
int st[100010],cnt,n,m;
int f(int p,int t){
    int i,m=1e8;
    if(p==n)return 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 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);
    for(;q--;){
        scanf("%d",&t.e);
      	t.s=1e9;
        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 8508 KB Output is correct
2 Correct 0 ms 8508 KB Output is correct
3 Correct 0 ms 8508 KB Output is correct
4 Correct 0 ms 8508 KB Output is correct
5 Correct 0 ms 8508 KB Output is correct
6 Correct 1 ms 8508 KB Output is correct
7 Correct 0 ms 8508 KB Output is correct
8 Correct 0 ms 8508 KB Output is correct
9 Correct 0 ms 8508 KB Output is correct
10 Correct 0 ms 8508 KB Output is correct
11 Correct 0 ms 8508 KB Output is correct
12 Correct 0 ms 8508 KB Output is correct
13 Correct 0 ms 8508 KB Output is correct
14 Correct 10 ms 8508 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 8508 KB Output is correct
2 Correct 25 ms 8508 KB Output is correct
3 Correct 31 ms 8508 KB Output is correct
4 Correct 0 ms 8508 KB Output is correct
5 Correct 6 ms 8508 KB Output is correct
6 Correct 4 ms 8508 KB Output is correct
7 Correct 17 ms 8508 KB Output is correct
8 Correct 2 ms 8508 KB Output is correct
9 Correct 22 ms 8508 KB Output is correct
10 Correct 0 ms 8508 KB Output is correct
11 Correct 16 ms 8508 KB Output is correct
12 Correct 32 ms 8508 KB Output is correct

Subtask #3
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 8508 KB Output is correct
2 Correct 200 ms 8508 KB Output is correct
3 Correct 189 ms 8508 KB Output is correct
4 Correct 178 ms 8508 KB Output is correct
5 Correct 179 ms 8508 KB Output is correct
6 Correct 293 ms 8508 KB Output is correct
7 Execution timed out 1000 ms 8508 KB Program timed out
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 8508 KB Output is correct
2 Correct 175 ms 8508 KB Output is correct
3 Correct 246 ms 8508 KB Output is correct
4 Correct 206 ms 8508 KB Output is correct
5 Correct 223 ms 8508 KB Output is correct
6 Correct 314 ms 8508 KB Output is correct
7 Execution timed out 1000 ms 8508 KB Program timed out
8 Halted 0 ms 0 KB -