oj.uz

Submission #43206

# Submission time Handle Problem Language Result Execution time Memory
43206 2018-03-10T22:15:44 Z smu201111192 버스 (JOI14_bus) C++14
35 / 100
 366 ms 144820 KB 
#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 = 2000005;
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)]);
    }
    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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 57592 KB Output is correct
2 Correct 50 ms 57708 KB Output is correct
3 Correct 51 ms 57968 KB Output is correct
4 Correct 57 ms 57968 KB Output is correct
5 Correct 55 ms 58028 KB Output is correct
6 Correct 51 ms 58028 KB Output is correct
7 Correct 51 ms 58076 KB Output is correct
8 Correct 51 ms 58076 KB Output is correct
9 Correct 50 ms 58076 KB Output is correct
10 Correct 50 ms 58076 KB Output is correct
11 Correct 53 ms 58364 KB Output is correct
12 Correct 53 ms 58416 KB Output is correct
13 Correct 53 ms 58592 KB Output is correct
14 Correct 53 ms 58592 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 58592 KB Output is correct
2 Correct 91 ms 59844 KB Output is correct
3 Correct 87 ms 60724 KB Output is correct
4 Correct 54 ms 60724 KB Output is correct
5 Correct 53 ms 60724 KB Output is correct
6 Correct 53 ms 60724 KB Output is correct
7 Correct 78 ms 60724 KB Output is correct
8 Correct 50 ms 60724 KB Output is correct
9 Correct 70 ms 61248 KB Output is correct
10 Correct 105 ms 62864 KB Output is correct
11 Correct 74 ms 63144 KB Output is correct
12 Correct 146 ms 64628 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 366 ms 141880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 361 ms 144820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -