oj.uz

Submission #25574

# Submission time Handle Problem Language Result Execution time Memory
25574 2017-06-23T05:55:05 Z 시제연(#1075) 버스 (JOI14_bus) C++
35 / 100
 1000 ms 59208 KB 
#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, c, q;
pii node[600100]; // node number, time
vector<pii> lis[600100];
vector<int> tis[100100];
map<pii,int> se;
pii ord[600100];
int dis[600100];
int INF = 987654321;

void dijk() {
    int i;
    priority_queue<pii> pq;
    for (i=0;i<c;i++) dis[i] = INF;
    for (i=0;i<c;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 loc(pii a) {
    return lower_bound(ord,ord+c,a)-ord;
}

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--;
        edg[i] = edge(a,b,c,d);
        tis[a].push_back(c);
        tis[b].push_back(d);
        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());
        tis[i].erase(unique(tis[i].begin(),tis[i].end()),tis[i].end());
    }
    sort(ord,ord+2*m);
    c = unique(ord,ord+2*m)-ord;
    for (i=0;i<m;i++) {
        int a = edg[i].a, b = edg[i].b, c = edg[i].c, d = edg[i].d;
        lis[loc(pii(a,c))].push_back(pii(d-c,loc(pii(b,d))));
    }
    for (i=0;i<n;i++) {
        for (j=(int)tis[i].size()-1;j>0;j--) {
            lis[loc(pii(i,tis[i][j-1]))].push_back(pii(tis[i][j]-tis[i][j-1],loc(pii(i,tis[i][j]))));
        }
    }
    dijk();
    /*
    for (i=0;i<c;i++) {
        for (j=0;j<lis[i].size();j++) {
            printf("%d (%d,%d) -> %d (%d,%d) : %d\n",i,ord[i].first+1,ord[i].second,
                                                     lis[i][j].second,ord[lis[i][j].second].first+1,
                                                     ord[lis[i][j].second].second,lis[i][j].first);
        }
    }
    for (i=0;i<c;i++) {
        printf("%d, %d : %d\n",ord[i].first+1,ord[i].second,dis[i]);
    }
    */
    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(),a)-tis[n-1].begin()-1;
        if (idx<0) {
            printf("-1\n");
            continue;
        }
        if (dis[loc(pii(n-1,tis[n-1][idx]))]>a) {
            printf("-1\n");
            continue;
        }
        printf("%d\n",tis[n-1][idx]-dis[loc(pii(n-1,tis[n-1][idx]))]);
    }

    return 0;
}

Compilation message

bus.cpp: In function 'void dijk()':
bus.cpp:40: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:60: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:63: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:99:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
bus.cpp:102:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a);
                       ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 34848 KB Output is correct
2 Correct 9 ms 34848 KB Output is correct
3 Correct 3 ms 34848 KB Output is correct
4 Correct 6 ms 34848 KB Output is correct
5 Correct 3 ms 34848 KB Output is correct
6 Correct 9 ms 34848 KB Output is correct
7 Correct 9 ms 34848 KB Output is correct
8 Correct 16 ms 34848 KB Output is correct
9 Correct 6 ms 34848 KB Output is correct
10 Correct 6 ms 34848 KB Output is correct
11 Correct 6 ms 34980 KB Output is correct
12 Correct 13 ms 34980 KB Output is correct
13 Correct 9 ms 35112 KB Output is correct
14 Correct 13 ms 34980 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 34848 KB Output is correct
2 Correct 49 ms 34848 KB Output is correct
3 Correct 43 ms 34848 KB Output is correct
4 Correct 13 ms 34848 KB Output is correct
5 Correct 13 ms 34848 KB Output is correct
6 Correct 9 ms 34848 KB Output is correct
7 Correct 29 ms 34848 KB Output is correct
8 Correct 3 ms 34848 KB Output is correct
9 Correct 29 ms 34848 KB Output is correct
10 Correct 73 ms 34980 KB Output is correct
11 Correct 39 ms 35112 KB Output is correct
12 Correct 59 ms 34980 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 933 ms 55968 KB Output is correct
2 Correct 913 ms 55968 KB Output is correct
3 Correct 953 ms 55968 KB Output is correct
4 Correct 836 ms 55968 KB Output is correct
5 Correct 816 ms 55968 KB Output is correct
6 Correct 936 ms 56116 KB Output is correct
7 Correct 959 ms 57148 KB Output is correct
8 Correct 933 ms 56508 KB Output is correct
9 Correct 809 ms 56128 KB Output is correct
10 Execution timed out 1000 ms 59208 KB Execution timed out
11 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 55968 KB Output is correct
2 Correct 913 ms 55968 KB Output is correct
3 Correct 819 ms 55968 KB Output is correct
4 Correct 863 ms 55968 KB Output is correct
5 Correct 879 ms 55968 KB Output is correct
6 Correct 946 ms 56116 KB Output is correct
7 Correct 889 ms 57148 KB Output is correct
8 Correct 883 ms 56120 KB Output is correct
9 Correct 826 ms 56128 KB Output is correct
10 Execution timed out 1000 ms 59208 KB Execution timed out
11 Halted 0 ms 0 KB -