Submission #56833

#	Time	Username	Problem	Language	Result	Execution time	Memory
56833		Hoppa	버스 (JOI14_bus)	C++14	100 / 100	935 ms	257820 KiB

bus

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int n,m,q,val;
vector<ii> g[100005];
struct data
{
    int u,v,ti,to;
} a[300005];
int cmp(data x,data y)
{
    return x.to<y.to;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>a[i].u>>a[i].v>>a[i].ti>>a[i].to;
    sort(a+1,a+1+m,cmp);
    for(int i=1; i<=m; i++)
    {
        if(a[i].u==1)
        {
            ii tmp=ii(a[i].to,a[i].ti);
            if(g[a[i].v].size()>0)
                tmp.second=max(tmp.second,g[a[i].v].back().second);
            g[a[i].v].push_back(tmp);
        }
        else
        {
            int rs=-1,l=0,r=g[a[i].u].size()-1;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(g[a[i].u][mid].first<=a[i].ti)
                {
                    rs=g[a[i].u][mid].second;
                    l=mid+1;
                }
                else r=mid-1;
            }
            if(rs!=-1)
            {
                ii tmp=ii(a[i].to,rs);
                if(g[a[i].v].size()>0)
                    tmp.second=max(tmp.second,g[a[i].v].back().second);
                g[a[i].v].push_back(tmp);
            }
        }
    }
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>val;
       int ans=-1,l=0,r=g[n].size()-1;
       while(l<=r)
       {
           int mid=(l+r)/2;
           if(g[n][mid].first<=val)
           {
               ans=g[n][mid].second;
               l=mid+1;
           }
           else r=mid-1;
       }
       cout<<ans<<"\n";
    }
}

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