oj.uz

Submission #25869

# Submission time Handle Problem Language Result Execution time Memory
25869 2017-06-24T16:02:19 Z model_code Price List (POI13_cen) C++11
100 / 100
 556 ms 24472 KB 
/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Cennik                                        *
 *   Autor:                Dawid Dabrowski                               *
 *   Zlozonosc czasowa:    O(m * sqrt(m))                                *
 *   Opis:                 Rozwiazanie wzorcowe                          *
 *                                                                       *
 *************************************************************************/

#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>

using namespace std;

const int MX = 100005;
const int INF = 1000000000;

int n, m, start, a, b;
vector<int> edges[MX], edges2[MX];	// [nr wierzcholka][parzystosc dlugosci sciezki od k],
// z edges2 bedziemy usuwac, edges nie ruszamy

set<pair<int, int> > edges_set;	// zbior wszystkich krawedzi, zeby sprawdzac, czy wierzcholki sa polaczone

int dist1[MX], dist2[MX];	// odleglosc kolejowa, odleglosc lotnicza
queue<int> Q;

void calc_dist1() {
    for (int i = 0; i < n; ++i) {
        dist1[i] = (i == start) ? 0 : INF;
    }
    Q.push(start);
    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        for (int i = 0; i < (int)edges[cur].size(); ++i) {
            if (dist1[edges[cur][i]] == INF) {
                dist1[edges[cur][i]] = dist1[cur] + 1;
                Q.push(edges[cur][i]);
            }
        }
    }
}

struct State {
    bool even;
    int current;
    int last; // tylko jesli even == true
    int dist;
    State(bool _even, int _current, int _last, int _dist):
        even(_even), current(_current), last(_last), dist(_dist) {}
};

queue<State> R;

void calc_dist2() {
    for (int i = 0; i < n; ++i) {
        dist2[i] = (i == start) ? 0 : INF;
    }
    R.push(State(true, start, -1, 0));
    while (!R.empty()) {
        State cur = R.front();
        R.pop();
        if (cur.even) {
            for (int i = 0; i < (int)edges[cur.current].size(); ++i) {
                R.push(State(false, edges[cur.current][i], cur.current, dist2[cur.current]));
            }
        } else {
            for (int i = 0; i < (int)edges2[cur.current].size(); ++i) {
                // czy mozemy przejsc ta krawedzia?
                if (edges_set.find(make_pair(cur.last, edges2[cur.current][i])) != edges_set.end()) {
                    // nie, nie robimy nic
                } else {
                    // tak, mozemy, przechodzimy nia i nie martwimy sie o nia juz wiecej, bo
                    // nie poprawi nic(!!!) ponowne rozpatrywanie jej
                    if (dist2[edges2[cur.current][i]] == INF) {
                        dist2[edges2[cur.current][i]] = cur.dist + 1;
                        R.push(State(true, edges2[cur.current][i], -1, cur.dist + 1));
                    }
                    swap(edges2[cur.current][i], edges2[cur.current].back());
                    edges2[cur.current].pop_back();
                    --i;
                }
            }
        }
    }
}

int main() {
    int ret = scanf("%d%d%d%d%d", &n, &m, &start, &a, &b);
    if (ret < 0) return 0;
    --start;
    for (int i = 0; i < m; ++i) {
        int u, v;
        ret = scanf("%d%d", &u, &v);
        --u;
        --v;
        edges[u].push_back(v);
        edges[v].push_back(u);
        edges2[u].push_back(v);
        edges2[v].push_back(u);
        edges_set.insert(make_pair(u, v));
        edges_set.insert(make_pair(v, u));
    }
    calc_dist1();
    calc_dist2();
    for (int i = 0; i < n; ++i) {
        if (dist1[i] % 2 == 0) {
            printf("%d\n", min(dist1[i] * a, (dist1[i] / 2) * b));
        } else {
            printf("%d\n",  min(dist1[i] * a,
                            min((dist1[i] / 2) * b + a,
                            (dist2[i] != INF) ? dist2[i] * b : INF)));
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9392 KB Output is correct
2 Correct 36 ms 9392 KB Output is correct
3 Correct 53 ms 9784 KB Output is correct
4 Correct 53 ms 9916 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 14284 KB Output is correct
2 Correct 113 ms 14284 KB Output is correct
3 Correct 153 ms 13084 KB Output is correct
4 Correct 203 ms 15328 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 19092 KB Output is correct
2 Correct 269 ms 17376 KB Output is correct
3 Correct 456 ms 20476 KB Output is correct
4 Correct 483 ms 21004 KB Output is correct
5 Correct 303 ms 20260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 21436 KB Output is correct
2 Correct 283 ms 17728 KB Output is correct
3 Correct 506 ms 21532 KB Output is correct
4 Correct 523 ms 21004 KB Output is correct
5 Correct 373 ms 21868 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 23696 KB Output is correct
2 Correct 439 ms 21796 KB Output is correct
3 Correct 529 ms 21928 KB Output is correct
4 Correct 499 ms 21004 KB Output is correct
5 Correct 413 ms 23296 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 22336 KB Output is correct
2 Correct 483 ms 22336 KB Output is correct
3 Correct 543 ms 22192 KB Output is correct
4 Correct 536 ms 21004 KB Output is correct
5 Correct 386 ms 24344 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 22984 KB Output is correct
2 Correct 466 ms 22852 KB Output is correct
3 Correct 556 ms 23116 KB Output is correct
4 Correct 516 ms 21004 KB Output is correct
5 Correct 419 ms 24472 KB Output is correct