oj.uz

Submission #16599

# Submission time Handle Problem Language Result Execution time Memory
16599 2015-08-29T11:28:14 Z eaststar 버스 (JOI14_bus) C++14
100 / 100
 310 ms 15452 KB 
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct data{
    int e,x,y;
    bool operator<(const data&r)const{
        return x<r.x;
    }
};
priority_queue<data> q[100010];
struct answer{
    int x,y;
    bool operator<(const answer&r)const{
        return y>r.y;
    }
};
vector<answer> ans;
int mn[100010],n;
int dfs(int p,int y){
    if(p==n)return y;
    while(!q[p].empty()&&q[p].top().x>=y){
        data t=q[p].top();
        q[p].pop();
        mn[p]=min(mn[p],dfs(t.e,t.y));
    }
    return mn[p];
}
int main(){
    int i,m,a,b,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i){
        scanf("%d%d%d%d",&a,&b,&x,&y);
        q[a].push({b,x,y});
    }
    for(i=1;i<=n;++i)mn[i]=1e8;
    while(!q[1].empty()){
        a=q[1].top().x;
        ans.push_back({a,dfs(1,a)});
    }
    scanf("%d",&m);
    for(;m--;){
        answer t;
        t.x=0;
        scanf("%d",&t.y);
        vector<answer>::iterator it=lower_bound(ans.begin(),ans.end(),t);
        printf("%d\n",it!=ans.end()?it->x:-1);
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4724 KB Output is correct
2 Correct 0 ms 4724 KB Output is correct
3 Correct 2 ms 4724 KB Output is correct
4 Correct 0 ms 4724 KB Output is correct
5 Correct 0 ms 4724 KB Output is correct
6 Correct 0 ms 4724 KB Output is correct
7 Correct 0 ms 4724 KB Output is correct
8 Correct 0 ms 4724 KB Output is correct
9 Correct 0 ms 4724 KB Output is correct
10 Correct 2 ms 4724 KB Output is correct
11 Correct 4 ms 4724 KB Output is correct
12 Correct 4 ms 4724 KB Output is correct
13 Correct 2 ms 4756 KB Output is correct
14 Correct 5 ms 4724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4724 KB Output is correct
2 Correct 39 ms 4724 KB Output is correct
3 Correct 49 ms 4724 KB Output is correct
4 Correct 6 ms 4724 KB Output is correct
5 Correct 9 ms 4724 KB Output is correct
6 Correct 0 ms 4724 KB Output is correct
7 Correct 38 ms 4724 KB Output is correct
8 Correct 0 ms 4724 KB Output is correct
9 Correct 15 ms 4724 KB Output is correct
10 Correct 43 ms 4724 KB Output is correct
11 Correct 27 ms 4756 KB Output is correct
12 Correct 43 ms 4724 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 10664 KB Output is correct
2 Correct 165 ms 10664 KB Output is correct
3 Correct 211 ms 10664 KB Output is correct
4 Correct 196 ms 10664 KB Output is correct
5 Correct 222 ms 10664 KB Output is correct
6 Correct 221 ms 10800 KB Output is correct
7 Correct 200 ms 10676 KB Output is correct
8 Correct 215 ms 11088 KB Output is correct
9 Correct 203 ms 10836 KB Output is correct
10 Correct 172 ms 11208 KB Output is correct
11 Correct 207 ms 11200 KB Output is correct
12 Correct 172 ms 11200 KB Output is correct
13 Correct 242 ms 11200 KB Output is correct
14 Correct 196 ms 11200 KB Output is correct
15 Correct 193 ms 11208 KB Output is correct
16 Correct 70 ms 15452 KB Output is correct
17 Correct 82 ms 15444 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 10664 KB Output is correct
2 Correct 253 ms 10664 KB Output is correct
3 Correct 310 ms 10664 KB Output is correct
4 Correct 247 ms 10664 KB Output is correct
5 Correct 266 ms 10664 KB Output is correct
6 Correct 248 ms 10800 KB Output is correct
7 Correct 215 ms 10676 KB Output is correct
8 Correct 244 ms 10796 KB Output is correct
9 Correct 235 ms 10836 KB Output is correct
10 Correct 243 ms 11208 KB Output is correct
11 Correct 215 ms 11200 KB Output is correct
12 Correct 220 ms 11332 KB Output is correct
13 Correct 208 ms 11208 KB Output is correct
14 Correct 234 ms 11200 KB Output is correct
15 Correct 236 ms 11208 KB Output is correct
16 Correct 76 ms 15444 KB Output is correct