oj.uz

Submission #25649

# Submission time Handle Problem Language Result Execution time Memory
25649 2017-06-23T10:57:15 Z tlwpdus 버스 (JOI14_bus) C++
100 / 100
 916 ms 67244 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, 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

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.0 / 20.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 34844 KB Output is correct
2 Correct 39 ms 34844 KB Output is correct
3 Correct 36 ms 34844 KB Output is correct
4 Correct 16 ms 34844 KB Output is correct
5 Correct 13 ms 34844 KB Output is correct
6 Correct 6 ms 34844 KB Output is correct
7 Correct 36 ms 34844 KB Output is correct
8 Correct 9 ms 34844 KB Output is correct
9 Correct 26 ms 34844 KB Output is correct
10 Correct 49 ms 35108 KB Output is correct
11 Correct 29 ms 35108 KB Output is correct
12 Correct 53 ms 35108 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 61904 KB Output is correct
2 Correct 733 ms 61904 KB Output is correct
3 Correct 653 ms 61904 KB Output is correct
4 Correct 706 ms 61904 KB Output is correct
5 Correct 559 ms 61904 KB Output is correct
6 Correct 613 ms 61912 KB Output is correct
7 Correct 743 ms 63812 KB Output is correct
8 Correct 693 ms 62260 KB Output is correct
9 Correct 649 ms 61920 KB Output is correct
10 Correct 906 ms 67228 KB Output is correct
11 Correct 916 ms 67240 KB Output is correct
12 Correct 826 ms 67240 KB Output is correct
13 Correct 809 ms 67240 KB Output is correct
14 Correct 799 ms 67240 KB Output is correct
15 Correct 859 ms 67244 KB Output is correct
16 Correct 236 ms 44216 KB Output is correct
17 Correct 229 ms 44216 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 61904 KB Output is correct
2 Correct 696 ms 61904 KB Output is correct
3 Correct 803 ms 61904 KB Output is correct
4 Correct 723 ms 61904 KB Output is correct
5 Correct 796 ms 61904 KB Output is correct
6 Correct 706 ms 61912 KB Output is correct
7 Correct 683 ms 63812 KB Output is correct
8 Correct 736 ms 61924 KB Output is correct
9 Correct 799 ms 61920 KB Output is correct
10 Correct 886 ms 67228 KB Output is correct
11 Correct 816 ms 67240 KB Output is correct
12 Correct 809 ms 67244 KB Output is correct
13 Correct 873 ms 67244 KB Output is correct
14 Correct 763 ms 67240 KB Output is correct
15 Correct 803 ms 67244 KB Output is correct
16 Correct 196 ms 44216 KB Output is correct