oj.uz

Submission #43219

# Submission time Handle Problem Language Result Execution time Memory
43219 2018-03-11T00:08:28 Z smu201111192 버스 (JOI14_bus) C++14
35 / 100
 1000 ms 92304 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++){
        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 45 ms 51320 KB Output is correct
2 Correct 47 ms 51424 KB Output is correct
3 Correct 53 ms 51460 KB Output is correct
4 Correct 47 ms 51460 KB Output is correct
5 Correct 47 ms 51476 KB Output is correct
6 Correct 47 ms 51476 KB Output is correct
7 Correct 45 ms 51492 KB Output is correct
8 Correct 46 ms 51492 KB Output is correct
9 Correct 47 ms 51492 KB Output is correct
10 Correct 45 ms 51620 KB Output is correct
11 Correct 50 ms 51728 KB Output is correct
12 Correct 54 ms 51752 KB Output is correct
13 Correct 49 ms 51796 KB Output is correct
14 Correct 48 ms 51796 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 51796 KB Output is correct
2 Correct 73 ms 52244 KB Output is correct
3 Correct 67 ms 52244 KB Output is correct
4 Correct 47 ms 52244 KB Output is correct
5 Correct 48 ms 52244 KB Output is correct
6 Correct 47 ms 52244 KB Output is correct
7 Correct 67 ms 52244 KB Output is correct
8 Correct 46 ms 52244 KB Output is correct
9 Correct 63 ms 52244 KB Output is correct
10 Correct 72 ms 52476 KB Output is correct
11 Correct 65 ms 52476 KB Output is correct
12 Correct 75 ms 52652 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 91576 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 1054 ms 92304 KB Time limit exceeded
2 Halted 0 ms 0 KB -