Submission #42387

#	Time	Username	Problem	Language	Result	Execution time	Memory
42387		dqhungdl	버스 (JOI14_bus)	C++14	100 / 100	392 ms	10796 KiB

bus

#include <bits/stdc++.h>
using namespace std;

struct data
{
    int u,v,s,t;
};

typedef pair<int,int> ii;
data Edge[300005];
int n,m,T;
vector<ii> g[100005];

bool cmp(data x1,data x2)
{
    return x1.t<x2.t;
}

int Binary(int u,int t)
{
    int rs=-1,l=0,r=g[u].size()-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(g[u][mid].first<=t)
        {
            rs=g[u][mid].second;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return rs;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>Edge[i].u>>Edge[i].v>>Edge[i].s>>Edge[i].t;
    sort(Edge+1,Edge+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(Edge[i].u==1)
        {
            ii tmp=ii(Edge[i].t,Edge[i].s);
            if(g[Edge[i].v].size()>0)
                tmp.second=max(tmp.second,g[Edge[i].v].back().second);
            g[Edge[i].v].push_back(tmp);
        }
        else
        {
            int t=Binary(Edge[i].u,Edge[i].s);
            if(t!=-1)
            {
                ii tmp=ii(Edge[i].t,t);;
                if(g[Edge[i].v].size()>0)
                    tmp.second=max(tmp.second,g[Edge[i].v].back().second);
                g[Edge[i].v].push_back(tmp);
            }
        }
    }
    cin>>T;
    int val;
    while(T--)
    {
        cin>>val;
        cout<<Binary(n,val)<<"\n";
    }
}

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