oj.uz

Submission #43220

# Submission time Handle Problem Language Result Execution time Memory
43220 2018-03-11T00:09:19 Z smu201111192 버스 (JOI14_bus) C++14
35 / 100
 1000 ms 92116 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[MAXV];
struct edge{
    int u,v,st,ed;
    void read(){
        cin>>u>>v>>st>>ed;
    }
}e[MAXV];
int dp[MAXV];
void addEdge(int u,int v){
    adj[v].push_back(u);
}
//n에 도착할 수 있는 가장 늦은 시점을 구하자.
vector<pair<int,int> > dd;
int dict(pair<int,int> c){
    return lower_bound(dd.begin(),dd.end(),c) - dd.begin() + 1;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        //e[i].read();
        cin >> e[i].u >> e[i].v >> e[i].st >> e[i].ed;
        dd.push_back({e[i].u,e[i].st});
        dd.push_back({e[i].v,e[i].ed});
        //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;
    sort(dd.begin(),dd.end());
    dd.erase(unique(dd.begin(),dd.end()),dd.end());
    for(int i = 0; i < dd.size(); i++){
        cv[i+1] = dd[i];
        ord.push_back({dd[i].second,i+1});
    }
//
//    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));
    vector<pair<int,int> > vc;
    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 == 1) vc.push_back(make_pair(dp[x],tm));
        if(pv == n)
            dp[x] = tm;
        for(auto y:adj[x])
            dp[y] = min(dp[y],dp[x]);
    }
    
    int Q; cin>> Q;
    sort(vc.begin(),vc.end());
    for(int i = 1; i <= Q; i++){
        if(n > 50000){
            if(i == 50000){
                assert(1);
            }
        }
        int tm; cin >> tm;
        if(vc.size() == 0){
            cout<<-1; continue;
        }
        int lo = 0;
        int hi = vc.size()-1;
        int ret = -1;
        while(lo <= hi){
            int mid = (lo+hi) / 2;
            if(vc[mid].first <= tm){
                lo = mid + 1;
                ret = max(ret,vc[mid].second);
            }
            else hi = mid - 1;
        }
        cout<<ret<<"\n";
    }
    
    return 0;
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < dd.size(); i++){
                      ^
bus.cpp:91: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 57 ms 51324 KB Output is correct
2 Correct 47 ms 51372 KB Output is correct
3 Correct 46 ms 51372 KB Output is correct
4 Correct 46 ms 51440 KB Output is correct
5 Correct 53 ms 51456 KB Output is correct
6 Correct 45 ms 51588 KB Output is correct
7 Correct 43 ms 51588 KB Output is correct
8 Correct 46 ms 51588 KB Output is correct
9 Correct 46 ms 51588 KB Output is correct
10 Correct 46 ms 51588 KB Output is correct
11 Correct 48 ms 51692 KB Output is correct
12 Correct 48 ms 51820 KB Output is correct
13 Correct 51 ms 51820 KB Output is correct
14 Correct 47 ms 51820 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 51820 KB Output is correct
2 Correct 66 ms 52336 KB Output is correct
3 Correct 71 ms 52348 KB Output is correct
4 Correct 50 ms 52348 KB Output is correct
5 Correct 47 ms 52348 KB Output is correct
6 Correct 48 ms 52348 KB Output is correct
7 Correct 64 ms 52348 KB Output is correct
8 Correct 47 ms 52348 KB Output is correct
9 Correct 60 ms 52348 KB Output is correct
10 Correct 69 ms 52508 KB Output is correct
11 Correct 64 ms 52508 KB Output is correct
12 Correct 79 ms 52636 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 91660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 92116 KB Time limit exceeded
2 Halted 0 ms 0 KB -