Submission #122454

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
122454	2019-06-28T10:46:38 Z	popovicirobert	Price List (POI13_cen)	C++14	60 / 100	4000 ms	9360 KB

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

/*
const int MOD = ;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}


inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}
*/

using namespace std;

const int MAXN = (int) 1e5;

vector <int> g[MAXN + 1];
ll dst[MAXN + 1];
bool vis[MAXN + 1], check[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, k, a, b;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> k >> a >> b;
    for(i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    memset(dst, 0x3f, sizeof(dst));

    if(a <= b) {
        queue <int> Q;
        Q.push(k);
        dst[k] = 0;

        while(Q.size()) {
            int nod = Q.front();
            Q.pop();

            for(auto it : g[nod]) {
                if(dst[it] > dst[nod] + 1) {
                    dst[it] = dst[nod] + 1;
                    Q.push(it);
                }
            }
        }

        for(i = 1; i <= n; i++) {
            cout << 1LL * min(2 * a, b) * (dst[i] / 2) + (dst[i] & 1) * a << "\n";
        }
        return 0;
    }

    priority_queue < pair <ll, int> > pq;
    pq.push({0, k});

    while(pq.size()) {
        auto cur = pq.top();
        pq.pop();

        if(vis[cur.second]) {
            continue;
        }

        vis[cur.second] = 1;
        dst[cur.second] = -cur.first;

        for(auto it : g[cur.second]) {
            check[it] = 1;
            if(dst[it] > a - cur.first) {
                dst[it] = a - cur.first;
                pq.push({-dst[it], it});
            }
        }

        if(2 * a > b) {
            for(auto it : g[cur.second]) {
                for(auto itr : g[it]) {
                    if(check[itr] == 0 && dst[itr] > b - cur.first) {
                        dst[itr] = b - cur.first;
                        pq.push({-dst[itr], itr});
                    }
                }
            }
        }

        for(auto it : g[cur.second]) {
            check[it] = 0;
        }

    }

    for(i = 1; i <= n; i++) {
        cout << dst[i] << "\n";
    }

    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3456 KB	Output is correct
2	Correct	4 ms	3456 KB	Output is correct
3	Correct	4 ms	3456 KB	Output is correct
4	Correct	4 ms	3456 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3484 KB	Output is correct
2	Correct	5 ms	3456 KB	Output is correct
3	Correct	5 ms	3456 KB	Output is correct
4	Correct	5 ms	3456 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	3584 KB	Output is correct
2	Correct	4 ms	3456 KB	Output is correct
3	Correct	6 ms	3556 KB	Output is correct
4	Correct	5 ms	3456 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	4156 KB	Output is correct
2	Correct	9 ms	4096 KB	Output is correct
3	Correct	13 ms	4224 KB	Output is correct
4	Correct	12 ms	4224 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	847 ms	6256 KB	Output is correct
2	Correct	21 ms	5624 KB	Output is correct
3	Correct	27 ms	5112 KB	Output is correct
4	Correct	30 ms	5624 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1155 ms	7820 KB	Output is correct
2	Correct	37 ms	6648 KB	Output is correct
3	Correct	74 ms	7464 KB	Output is correct
4	Correct	53 ms	7288 KB	Output is correct
5	Correct	3003 ms	8152 KB	Output is correct

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1676 ms	8540 KB	Output is correct
2	Correct	39 ms	6780 KB	Output is correct
3	Correct	73 ms	7672 KB	Output is correct
4	Correct	49 ms	7292 KB	Output is correct
5	Execution timed out	4030 ms	8908 KB	Time limit exceeded

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1157 ms	9360 KB	Output is correct
2	Correct	57 ms	8184 KB	Output is correct
3	Correct	82 ms	7932 KB	Output is correct
4	Correct	65 ms	7288 KB	Output is correct
5	Execution timed out	4013 ms	9072 KB	Time limit exceeded

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	305 ms	8688 KB	Output is correct
2	Correct	49 ms	8312 KB	Output is correct
3	Correct	85 ms	8184 KB	Output is correct
4	Correct	62 ms	7308 KB	Output is correct
5	Execution timed out	4021 ms	9124 KB	Time limit exceeded

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	7672 KB	Output is correct
2	Correct	59 ms	7516 KB	Output is correct
3	Correct	85 ms	7672 KB	Output is correct
4	Correct	56 ms	6264 KB	Output is correct
5	Execution timed out	4088 ms	9344 KB	Time limit exceeded

Submission #122454

Compilation message