Submission #16599

#	Time	Username	Problem	Language	Result	Execution time	Memory
16599		eaststar	버스 (JOI14_bus)	C++14	100 / 100	310 ms	15452 KiB

bus

#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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50