oj.uz

Submission #43221

# Submission time Handle Problem Language Result Execution time Memory
43221 2018-03-11T00:10:28 Z smu201111192 버스 (JOI14_bus) C++14
35 / 100
 1000 ms 91692 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);
}
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++){
        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});
        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(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;
    int iter = 0;
    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]);
            iter++;
        }
    }
    assert(iter < 2000000);
    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:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < dd.size(); i++){
                      ^
bus.cpp:80: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 45 ms 51320 KB Output is correct
3 Correct 44 ms 51356 KB Output is correct
4 Correct 48 ms 51404 KB Output is correct
5 Correct 47 ms 51440 KB Output is correct
6 Correct 46 ms 51440 KB Output is correct
7 Correct 43 ms 51504 KB Output is correct
8 Correct 46 ms 51504 KB Output is correct
9 Correct 48 ms 51504 KB Output is correct
10 Correct 45 ms 51504 KB Output is correct
11 Correct 48 ms 51756 KB Output is correct
12 Correct 48 ms 51756 KB Output is correct
13 Correct 48 ms 51756 KB Output is correct
14 Correct 48 ms 51756 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 51756 KB Output is correct
2 Correct 68 ms 52264 KB Output is correct
3 Correct 71 ms 52264 KB Output is correct
4 Correct 51 ms 52264 KB Output is correct
5 Correct 49 ms 52264 KB Output is correct
6 Correct 48 ms 52264 KB Output is correct
7 Correct 63 ms 52264 KB Output is correct
8 Correct 45 ms 52264 KB Output is correct
9 Correct 63 ms 52264 KB Output is correct
10 Correct 72 ms 52492 KB Output is correct
11 Correct 65 ms 52492 KB Output is correct
12 Correct 71 ms 52720 KB Output is correct

Subtask #3
0 / 15.0

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