oj.uz

답안 #122468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122468 2019-06-28T11:12:53 Z popovicirobert Price List (POI13_cen) C++14
100 / 100
 332 ms 28388 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 INF = 1e9;
const int MAXN = (int) 1e5;

vector <int> g[MAXN + 1];
int dstA[MAXN + 1], dstB[MAXN + 1];
int n, m, k, a, b;

inline void bfsA() {
    fill(dstA + 1, dstA + n + 1, INF);

    queue <int> Q;
    Q.push(k);
    dstA[k] = 0;

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

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

set <int> mst[MAXN + 1];
vector <int> activ[MAXN + 1];

inline void bfsB() {
    fill(dstB + 1, dstB + n + 1, INF);

    queue <int> Q;
    Q.push(k);
    dstB[k] = 0;

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

        for(auto it : g[nod]) {
            vector <int> cur;
            for(auto itr : activ[it]) {
                if(dstB[itr] != INF) {
                    continue;
                }
                if(mst[nod].find(itr) == mst[nod].end()) {
                    dstB[itr] = dstB[nod] + 1;
                    Q.push(itr);
                }
                else {
                    cur.push_back(itr);
                }
            }
            swap(cur, activ[it]);
        }
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i;
    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);
        mst[x].insert(y), mst[y].insert(x);
        activ[x].push_back(y), activ[y].push_back(x);
    }

    bfsA();
    bfsB();

    for(i = 1; i <= n; i++) {
        if(dstA[i] % 2 == 0) {
            cout << min(1LL * b * dstA[i] / 2, 1LL * a * dstA[i]) << "\n";
        }
        else {
            cout << min(1LL * dstB[i] * b, min(1LL * dstA[i] * a, 1LL * (dstA[i] / 2) * b + (dstA[i] & 1) * a)) << "\n";
        }
    }

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9816 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9792 KB Output is correct
2 Correct 14 ms 9848 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 12 ms 9852 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 12024 KB Output is correct
2 Correct 22 ms 11916 KB Output is correct
3 Correct 34 ms 12508 KB Output is correct
4 Correct 29 ms 12536 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 17108 KB Output is correct
2 Correct 85 ms 17140 KB Output is correct
3 Correct 78 ms 16248 KB Output is correct
4 Correct 118 ms 18884 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 22816 KB Output is correct
2 Correct 144 ms 21188 KB Output is correct
3 Correct 245 ms 24772 KB Output is correct
4 Correct 308 ms 25500 KB Output is correct
5 Correct 176 ms 23548 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 25372 KB Output is correct
2 Correct 153 ms 21752 KB Output is correct
3 Correct 251 ms 26068 KB Output is correct
4 Correct 261 ms 25700 KB Output is correct
5 Correct 163 ms 25428 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 28172 KB Output is correct
2 Correct 212 ms 26360 KB Output is correct
3 Correct 260 ms 26744 KB Output is correct
4 Correct 256 ms 25436 KB Output is correct
5 Correct 192 ms 27156 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 258 ms 27128 KB Output is correct
2 Correct 252 ms 27128 KB Output is correct
3 Correct 313 ms 27116 KB Output is correct
4 Correct 296 ms 25568 KB Output is correct
5 Correct 221 ms 28268 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 27996 KB Output is correct
2 Correct 209 ms 27924 KB Output is correct
3 Correct 332 ms 28188 KB Output is correct
4 Correct 264 ms 25636 KB Output is correct
5 Correct 214 ms 28388 KB Output is correct