oj.uz

Submission #43214

# Submission time Handle Problem Language Result Execution time Memory
43214 2018-03-10T23:52:41 Z smu201111192 버스 (JOI14_bus) C++14
35 / 100
 318 ms 86568 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 = 1000005;
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[v].push_back(u);
}
//n에 도착할 수 있는 가장 늦은 시점을 구하자.
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        e[i].read();
        dict[{e[i].u,e[i].st}];
        dict[{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());
    }
    vector<pair<int,int> > ord;
    for(auto it = dict.begin(); it!= dict.end(); it++){
        it->second = ++id;
        cv[id] = it->first;
        ord.push_back({it->first.second,id});
    }
    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;
        addEdge(dict[{u,st}],dict[{v,ed}]);
    }
    sort(ord.begin(),ord.end());
    reverse(ord.begin(),ord.end());
    memset(dp,0x3f3f3f3f,sizeof(dp));
    
    for(int i = 0; i<ord.size();i++){
        int x = ord[i].second;
        int tm = ord[i].first;
        int pv = cv[x].first;
        if(pv == n)
            dp[x] = tm;
        for(auto y:adj[x])
            dp[y] = min(dp[y],dp[x]);
    }
    
    int Q; cin>> Q;
    if(Q > 10000){
        assert(1);
    }
    for(int i = 1; i <= Q; i++){
        int tm; cin >> tm;
        if(node[1].size() == 0) {
            cout<<-1; continue;
        }
        int lo = 0; int hi = node[1].size() - 1;
        int ret = -1;
        while(lo <= hi){
            int mid = (lo + hi)/2;
            int t = node[1][mid];
            //요시간에 출발하면 언제 도착혀?
            int v = dict[{1,t}];
            if(dp[v] <= tm){
                ret = max(ret,t);
                lo = mid + 1;
            }
            else hi = mid - 1;
        }
        cout<<ret<<"\n";
    }
    
    return 0;
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<ord.size();i++){
                     ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30200 KB Output is correct
2 Correct 27 ms 30304 KB Output is correct
3 Correct 27 ms 30376 KB Output is correct
4 Correct 29 ms 30376 KB Output is correct
5 Correct 26 ms 30376 KB Output is correct
6 Correct 26 ms 30484 KB Output is correct
7 Correct 29 ms 30556 KB Output is correct
8 Correct 27 ms 30556 KB Output is correct
9 Correct 29 ms 30556 KB Output is correct
10 Correct 27 ms 30556 KB Output is correct
11 Correct 31 ms 30828 KB Output is correct
12 Correct 31 ms 30828 KB Output is correct
13 Correct 30 ms 30828 KB Output is correct
14 Correct 31 ms 30828 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30828 KB Output is correct
2 Correct 66 ms 31212 KB Output is correct
3 Correct 65 ms 31212 KB Output is correct
4 Correct 31 ms 31212 KB Output is correct
5 Correct 31 ms 31212 KB Output is correct
6 Correct 41 ms 31212 KB Output is correct
7 Correct 55 ms 31212 KB Output is correct
8 Correct 27 ms 31212 KB Output is correct
9 Correct 46 ms 31212 KB Output is correct
10 Correct 74 ms 31532 KB Output is correct
11 Correct 48 ms 31532 KB Output is correct
12 Correct 114 ms 31688 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 296 ms 86568 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 318 ms 86568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -