Submission #25649

#	Time	Username	Problem	Language	Result	Execution time	Memory
25649		tlwpdus	버스 (JOI14_bus)	C++98	100 / 100	916 ms	67244 KiB

bus

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<pii,int> piii;

struct edge {
    int a, b, c, d;
    edge(){}
    edge(int a, int b, int c, int d):a(a),b(b),c(c),d(d){}
};

edge edg[300100];
int n, m, q;
pii node[600100]; // node number, time
vector<pii> lis[600100];
vector<piii> tis[100100];
pii ord[600100];
int dis[600100];
int INF = 987654321;

void dijk() {
    int i;
    priority_queue<pii> pq;
    for (i=0;i<2*m;i++) dis[i] = INF;
    for (i=0;i<2*m;i++) {
        if (ord[i].first==0) {
            dis[i] = 0;
            pq.push(pii(0,i));
        }
    }
    while(!pq.empty()) {
        pii tmp = pq.top();
        pq.pop();
        int here = tmp.second;
        int d = -tmp.first;
        if (dis[here]!=d) continue;
        for (i=0;i<lis[here].size();i++) {
            int there = lis[here][i].second;
            int w = lis[here][i].first;
            if (dis[there]>dis[here]+w) {
                dis[there]=dis[here]+w;
                pq.push(pii(-dis[there],there));
            }
        }
    }
}

int main() {
    int i, j;

    //freopen("input","r",stdin);

    scanf("%d%d",&n,&m);
    for (i=0;i<m;i++) {
        int a, b, c, d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        a--;b--;
        tis[ a ].push_back(piii(pii(c,1),i*2));
        tis[ b ].push_back(piii(pii(d,0),i*2+1));
        lis[i*2].push_back(pii(d-c,i*2+1));
        ord[ i*2 ] = pii(a,c);
        ord[i*2+1] = pii(b,d);
    }
    for (i=0;i<n;i++) sort(tis[i].begin(),tis[i].end());
    for (i=0;i<n;i++) {
        for (j=1;j<tis[i].size();j++) {
            lis[tis[i][j-1].second].push_back(pii(tis[i][j].first.first-tis[i][j-1].first.first,tis[i][j].second));
        }
    }
    dijk();
    scanf("%d",&q);
    for (i=0;i<q;i++) {
        int a;
        scanf("%d",&a);
        int idx = upper_bound(tis[n-1].begin(),tis[n-1].end(),piii(pii(a,2),987654321))-tis[n-1].begin()-1;
        if (idx<0) {
            printf("-1\n");
            continue;
        }
        if (dis[tis[n-1][idx].second]>a) {
            printf("-1\n");
            continue;
        }
        printf("%d\n",tis[n-1][idx].first.first-dis[tis[n-1][idx].second]);
    }

    return 0;
}

Compilation message (stderr)

bus.cpp: In function 'void dijk()':
bus.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<lis[here].size();i++) {
                   ^
bus.cpp: In function 'int main()':
bus.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=1;j<tis[i].size();j++) {
                   ^
bus.cpp:55:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
bus.cpp:58:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d",&a,&b,&c,&d);
                                      ^
bus.cpp:73:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
bus.cpp:76:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a);
                       ^

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50