제출 #43209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43209		smu201111192	버스 (JOI14_bus)	C++14	35 / 100	302 ms	62992 KiB

bus

#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 100005;
const int MAXV = 500005;
int n,m,id = 0;
map<pair<int,int>,int> dict;
pair<int,int> cv[MAXV];
vector<int> adj[MAXV];
vector<int> node[MAXN];
struct edge{
    int u,v,st,ed;
    void read(){cin>>u>>v>>st>>ed;}
}e[MAXN];
int dp[MAXV];
void addEdge(int u,int v){
    adj[u].push_back(v);
}
int go(int cur){
    int v = cv[cur].first;
    int tm = cv[cur].second;
    if(v == n) return tm;
    int &ret = dp[cur];
    if(ret != -1) return ret;
    ret = 2e9;
    for(auto x : adj[cur]){
        ret = min(ret,go(x));
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    node[1].push_back(0);
    for(int i = 1; i <= m; i++){
        e[i].read();
        dict[make_pair(e[i].u,e[i].st)];
        dict[make_pair(e[i].v,e[i].ed)];
        node[e[i].u].push_back(e[i].st);
        node[e[i].v].push_back(e[i].ed);
    }
    for(int i = 1; i <= n; i++) {
        sort(node[i].begin(),node[i].end());
        node[i].erase(unique(node[i].begin(),node[i].end()),node[i].end());
    }
    dict[make_pair(1,0)];
    for(auto it = dict.begin(); it!= dict.end(); it++){
        it->second = ++id;
        cv[id] = it->first;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < (int)node[i].size() - 1; j++){
            int tu = node[i][j];
            int tv = node[i][j+1];
            addEdge(dict[make_pair(i,tu)],dict[make_pair(i,tv)]);
        }
    }
    for(int i = 1; i <= m; i++){
        int u = e[i].u; int v = e[i].v;
        int st = e[i].st; int ed = e[i].ed;
        adj[dict[make_pair(u,st)]].push_back(dict[make_pair(v,ed)]);
    }
    assert(id<MAXV);
    memset(dp,-1,sizeof(dp));
    int q; cin >> q;
    for(int i = 1;i <= q; i++){
        int goal; cin >> goal;
        int low = 0;
        int high = node[1].size()-1;
        int ans = -1;
        while(low <= high){
            int mid = (low+high)/2;
            int id = dict[make_pair(1,node[1][mid])];
            if(go(id) <= goal){
                ans = max(ans,node[1][mid]);
                low = mid + 1;
            }
            else high = mid - 1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

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