oj.uz

Submission #43218

# Submission time Handle Problem Language Result Execution time Memory
43218 2018-03-11T00:03:51 Z smu201111192 버스 (JOI14_bus) C++14
35 / 100
 1000 ms 102128 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에 도착할 수 있는 가장 늦은 시점을 구하자.
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;
        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));
    
    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:78: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 44 ms 51320 KB Output is correct
2 Correct 46 ms 51424 KB Output is correct
3 Correct 43 ms 51496 KB Output is correct
4 Correct 45 ms 51496 KB Output is correct
5 Correct 44 ms 51496 KB Output is correct
6 Correct 45 ms 51572 KB Output is correct
7 Correct 46 ms 51572 KB Output is correct
8 Correct 46 ms 51644 KB Output is correct
9 Correct 45 ms 51644 KB Output is correct
10 Correct 49 ms 51644 KB Output is correct
11 Correct 51 ms 51900 KB Output is correct
12 Correct 50 ms 51948 KB Output is correct
13 Correct 49 ms 52076 KB Output is correct
14 Correct 49 ms 52076 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 52076 KB Output is correct
2 Correct 68 ms 52480 KB Output is correct
3 Correct 79 ms 52480 KB Output is correct
4 Correct 49 ms 52480 KB Output is correct
5 Correct 47 ms 52480 KB Output is correct
6 Correct 47 ms 52480 KB Output is correct
7 Correct 70 ms 52480 KB Output is correct
8 Correct 43 ms 52480 KB Output is correct
9 Correct 61 ms 52480 KB Output is correct
10 Correct 75 ms 52764 KB Output is correct
11 Correct 64 ms 52764 KB Output is correct
12 Correct 74 ms 52908 KB Output is correct

Subtask #3
0 / 15.0

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