Submission #43222

#	Time	Username	Problem	Language	Result	Execution time	Memory
43222		smu201111192	버스 (JOI14_bus)	C++14	35 / 100	1014 ms	92472 KiB

bus

#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 (stderr)

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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 50