Submission #16600

#	Time	Username	Problem	Language	Result	Execution time	Memory
16600		eaststar	버스 (JOI14_bus)	C++14	100 / 100	321 ms	18304 KiB

bus

#include <bits/stdc++.h>
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;
    }
}ans[300010];
int mn[100010],n,cnt;
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[cnt++]={a,dfs(1,a)};
    }
    scanf("%d",&m);
    for(;m--;){
        answer t;
        t.x=0;
        scanf("%d",&t.y);
        i=lower_bound(ans,ans+cnt,t)-ans;
        printf("%d\n",i<cnt?ans[i].x:-1);
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50