oj.uz

답안 #43222

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43222 2018-03-11T00:14:59 Z smu201111192 버스 (JOI14_bus) C++14
35 / 100
 1000 ms 92472 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;
namespace fio {
    const int BSIZE = 1<<17;
    unsigned char buffer[BSIZE];
    unsigned char *p = buffer + BSIZE;
    inline unsigned char readChar() {
        if (p == buffer + BSIZE) {
            fread(buffer, 1, 1 << 17, stdin);
            p = buffer;
        }
        return *p++;
    }
    int readInt() {
        unsigned char c = readChar();
        while (c<'-')c = readChar();
        int ret = 0;
        do {
            ret = ret * 10 + c - '0';
            c = readChar();
        } while (c >='-');
        return ret;
    }
}
//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;
}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);
    n =fio::readInt();
    m = fio::readInt();
    //cin >> n >> m;
    for(int i = 1; i <= m; i++){
        e[i].u = fio::readInt();
        e[i].v = fio::readInt();
        e[i].st = fio::readInt();
        e[i].ed = fio::readInt();
        //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;
     Q = fio::readInt();
    sort(vc.begin(),vc.end());
    for(int i = 1; i <= Q; i++){
    
        int tm;
        tm = fio::readInt();
        //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;
        }
        printf("%d\n",ret);
        //cout<<ret<<"\n";
    }
    
    return 0;
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < dd.size(); i++){
                      ^
bus.cpp:105:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<ord.size();i++){
                     ^
bus.cpp: In function 'unsigned char fio::readChar()':
bus.cpp:30:45: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buffer, 1, 1 << 17, stdin);
                                             ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 51320 KB Output is correct
2 Correct 46 ms 51320 KB Output is correct
3 Correct 47 ms 51448 KB Output is correct
4 Correct 46 ms 51448 KB Output is correct
5 Correct 46 ms 51484 KB Output is correct
6 Correct 47 ms 51492 KB Output is correct
7 Correct 47 ms 51492 KB Output is correct
8 Correct 47 ms 51552 KB Output is correct
9 Correct 55 ms 51552 KB Output is correct
10 Correct 49 ms 51552 KB Output is correct
11 Correct 46 ms 51804 KB Output is correct
12 Correct 46 ms 51820 KB Output is correct
13 Correct 46 ms 51820 KB Output is correct
14 Correct 45 ms 51820 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 51820 KB Output is correct
2 Correct 58 ms 52464 KB Output is correct
3 Correct 62 ms 52476 KB Output is correct
4 Correct 47 ms 52476 KB Output is correct
5 Correct 46 ms 52476 KB Output is correct
6 Correct 46 ms 52476 KB Output is correct
7 Correct 55 ms 52476 KB Output is correct
8 Correct 54 ms 52476 KB Output is correct
9 Correct 66 ms 52476 KB Output is correct
10 Correct 67 ms 52524 KB Output is correct
11 Correct 56 ms 52524 KB Output is correct
12 Correct 63 ms 52732 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1014 ms 91700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1002 ms 92472 KB Time limit exceeded
2 Halted 0 ms 0 KB -