Submission #1192690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192690		vnedu	버스 (JOI14_bus)	C++17	100 / 100	92 ms	12744 KiB

bus

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

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 10;
const int M = 3e5 + 10;
const int inf = 1e9;
struct Edge
{
    int u,v,x,y;
    Edge() {}
    void input()
    {
        cin>>u>>v>>x>>y;
    }
} edge[M];
int numNode,numEdge,best[M];
vector<int> adj[N];
bool cmp(int id1, int id2)
{
    return edge[id1].y>edge[id2].y;
}
queue<int> q;
ii cur[M];
int suf[M];
void solve()
{
    cin>>numNode>>numEdge;
    for(int i=1;i<=numEdge;++i)
    {
        Edge &cm=edge[i];
        cm.input();
        adj[cm.v].pb(i);
        best[i]=inf;
    }
    for(int i=1;i<=numNode;++i) sort(all(adj[i]),cmp);
    while(!adj[numNode].empty())
    {
        q.push(adj[numNode].back());
        int curCost=edge[adj[numNode].back()].y;
        adj[numNode].pop_back();
        while(!q.empty())
        {
            int id=q.front(); q.pop();
//            cout<<edge[id].v<<' '<<edge[id].u<<'\n';
            minimize(best[id],curCost);
            int u=edge[id].u;
            while(!adj[u].empty())
            {
//                cout<<"DSA";
                int id2=adj[u].back();
                if(edge[id2].y>edge[id].x) break;
                adj[u].pop_back();
                q.push(id2);
            }
        }
    }
//    for(int i=1;i<=numEdge;++i)
//    {
//        Edge &cm=edge[i];
//        cout<<cm.u<<' '<<cm.v<<' '<<cm.x<<' '<<cm.y<<' '<<best[i]<<'\n';
//    }
//    return;
    int ptr=0;
    for(int i=1;i<=numEdge;++i) if(edge[i].u==1) cur[++ptr]=make_pair(edge[i].x,best[i]);
    sort(cur+1,cur+1+ptr);
    suf[ptr+1]=inf;
    for(int i=ptr;i>=1;--i) suf[i]=min(suf[i+1],cur[i].se);
    int numQuery; cin>>numQuery;
    while(numQuery--)
    {
        int t; cin>>t;
        int pos=lower_bound(suf+1,suf+1+ptr,t+1)-suf-1;
        cout<<(pos==0?-1:cur[pos].fi)<<'\n';
    }
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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