Submission #25871

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
25871	2017-06-24T16:02:49 Z	model_code	Price List (POI13_cen)	C++11	100 / 100	2883 ms	15512 KB

/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Cennik                                        *
 *   Autor:                Karol Pokorski                                *
 *   Opis:                 Rozwiazanie powolne, wzorcowka bez usuwania   *
 *                         niepotrzebnych krawedzi po ich przejrzeniu    *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

#define F first
#define S second
typedef long long int LL;

const int MAXN = 100001;
const int MAXM = 100001;
const int INF = 1000000001;

struct TState {
    // stan - zgodnie z rozwiazaniem wzorcowym
    pair<int,int> p;
    int dist;

    TState(int,int,int);
};

TState::TState(int a, int b, int c) {
    p.F = a;
    p.S = b;
    dist = c;
}

vector<pair<int,int> > adj[MAXN], sadj[MAXN];
queue<TState> Q;
int d1[MAXN], d2[MAXN];
bool vis1[MAXM], vis2[MAXM];

bool CheckExistence(int u, int v) {
    // sprawdzenie wyszukiwaniem binarnym czy krawedz (u, v) istnieje
    int fromSearch = 0, toSearch = (int)sadj[u].size()-1;

    while (fromSearch < toSearch) {
        int centSearch = (fromSearch+toSearch)/2;

        if (sadj[u][centSearch].F < v)
            fromSearch = centSearch+1;
        else
            toSearch = centSearch;
    }

    return (sadj[u][fromSearch].F == v);
}

int main() {
    int ret, n, m, s, e1, e2;

    ret = scanf("%d%d%d%d%d", &n, &m, &s, &e1, &e2);
    if (ret < 0) return 0;
    s--;

    for (int i = 0; i < m; i++) {
        int u, v;

        ret = scanf("%d%d", &u, &v);
        u--;
        v--;

        adj[u].push_back(make_pair(v, 2*i));
        adj[v].push_back(make_pair(u, 2*i+1));
        sadj[u].push_back(make_pair(v, 2*i));
        sadj[v].push_back(make_pair(u, 2*i+1));
    }

    for (int i = 0; i < n; i++) {
        sort(adj[i].begin(), adj[i].end());
        sort(sadj[i].begin(), sadj[i].end());
    }

    fill(d1, d1+n, INF);
    fill(d2, d2+n, INF);

    vis1[s] = true;
    d1[s] = 0;

    Q.push(TState(s, -1, 0));
    while (!Q.empty()) {
        TState state = Q.front();
        int u = state.p.F, dist = state.dist;

        Q.pop();

        for (int i = 0; i < (int)adj[u].size(); i++)
            if (!vis1[adj[u][i].F]) {
                Q.push(TState(adj[u][i].F, 0, dist+1));
                d1[adj[u][i].F] = dist+1;
                vis1[adj[u][i].F] = true;
            }
    }

    vis2[s] = true;
    d2[s] = 0;

    Q.push(TState(s, -1, 0));
    while (!Q.empty()) {
        TState state = Q.front();
        int u = state.p.F, v = state.p.S, dist = state.dist;

        Q.pop();

        if (v == -1) {
            for (int i = 0; i < (int)sadj[u].size(); i++)
                Q.push(TState(adj[u][i].F, u, dist+1));
        }
        else {
            for (int i = 0; i < (int)adj[u].size(); i++)
                if ((!vis2[adj[u][i].F]) && (!CheckExistence(v, adj[u][i].F))) {
                    Q.push(TState(adj[u][i].F, -1, dist+1));
                    d2[adj[u][i].F] = dist+1;
                    vis2[adj[u][i].F] = true;
                }
        }
    }

    for (int i = 0; i < n; i++) {
        if (d1[i]%2 == 0)
            printf("%lld\n", min((LL)d1[i]*e1, (LL)(d1[i]/2)*e2));
        else
            printf("%lld\n", min(min((LL)d1[i]*e1, (LL)(d1[i]/2)*e2+e1), (LL)(d2[i]/2)*e2));
    }

    return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	7600 KB	Output is correct
2	Correct	7600 KB	Output is correct
3	Correct	7600 KB	Output is correct
4	Correct	7600 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	7600 KB	Output is correct
2	Correct	7600 KB	Output is correct
3	Correct	7600 KB	Output is correct
4	Correct	7600 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	8524 KB	Output is correct
2	Correct	26 ms	8524 KB	Output is correct
3	Correct	13 ms	8788 KB	Output is correct
4	Correct	19 ms	8656 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	589 ms	10896 KB	Output is correct
2	Correct	589 ms	10896 KB	Output is correct
3	Correct	63 ms	10372 KB	Output is correct
4	Correct	89 ms	10900 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	653 ms	12820 KB	Output is correct
2	Correct	249 ms	11904 KB	Output is correct
3	Correct	176 ms	13804 KB	Output is correct
4	Correct	203 ms	13144 KB	Output is correct
5	Correct	1729 ms	13696 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1016 ms	13716 KB	Output is correct
2	Correct	129 ms	11824 KB	Output is correct
3	Correct	189 ms	14332 KB	Output is correct
4	Correct	186 ms	13144 KB	Output is correct
5	Correct	2206 ms	14480 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	713 ms	14636 KB	Output is correct
2	Correct	236 ms	13592 KB	Output is correct
3	Correct	189 ms	14464 KB	Output is correct
4	Correct	223 ms	13144 KB	Output is correct
5	Correct	2613 ms	14988 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	256 ms	13836 KB	Output is correct
2	Correct	249 ms	13836 KB	Output is correct
3	Correct	109 ms	14596 KB	Output is correct
4	Correct	186 ms	13144 KB	Output is correct
5	Correct	2653 ms	15436 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	183 ms	13804 KB	Output is correct
2	Correct	103 ms	13804 KB	Output is correct
3	Correct	129 ms	14860 KB	Output is correct
4	Correct	206 ms	13144 KB	Output is correct
5	Correct	2883 ms	15512 KB	Output is correct

Submission #25871

Compilation message