oj.uz

Submission #25580

# Submission time Handle Problem Language Result Execution time Memory
25580 2017-06-23T06:06:46 Z 시제연(#1075) 버스 (JOI14_bus) C++
20 / 100
 1000 ms 58708 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];
pii ord[600100];
int dis[600100];
int deg[600100];
int INF = 987654321;

void dijk() {
    int i;
    queue<int> 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(i);
        }
        else if (deg[i]==0) {
            pq.push(i);
        }
    }
    while(!pq.empty()) {
        int here = pq.front();
        pq.pop();
        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;
            deg[there]--;
            if (deg[there]==0) pq.push(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;
        int p = loc(pii(a,c)), q = loc(pii(b,d));
        lis[p].push_back(pii(d-c,q)); deg[q]++;
    }
    for (i=1;i<n;i++) {
        for (j=(int)tis[i].size()-1;j>0;j--) {
            int p = loc(pii(i,tis[i][j-1])), q = loc(pii(i,tis[i][j]));
            lis[p].push_back(pii(tis[i][j]-tis[i][j-1],q)); deg[q]++;
        }
    }
    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:59: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:62: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:100:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
bus.cpp:103: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 3 ms 37192 KB Output is correct
2 Correct 3 ms 37192 KB Output is correct
3 Correct 0 ms 37192 KB Output is correct
4 Correct 6 ms 37192 KB Output is correct
5 Correct 3 ms 37192 KB Output is correct
6 Correct 6 ms 37192 KB Output is correct
7 Correct 9 ms 37192 KB Output is correct
8 Correct 6 ms 37192 KB Output is correct
9 Correct 3 ms 37192 KB Output is correct
10 Correct 6 ms 37192 KB Output is correct
11 Correct 6 ms 37324 KB Output is correct
12 Correct 16 ms 37324 KB Output is correct
13 Correct 13 ms 37456 KB Output is correct
14 Correct 9 ms 37324 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37192 KB Output is correct
2 Correct 56 ms 37192 KB Output is correct
3 Correct 59 ms 37192 KB Output is correct
4 Correct 19 ms 37192 KB Output is correct
5 Correct 13 ms 37192 KB Output is correct
6 Correct 13 ms 37192 KB Output is correct
7 Correct 26 ms 37192 KB Output is correct
8 Incorrect 6 ms 37192 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 58708 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 58708 KB Execution timed out
2 Halted 0 ms 0 KB -