Submission #102627

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
102627	2019-03-26T10:00:43 Z	someone_aa	Price List (POI13_cen)	C++17	100 / 100	471 ms	28640 KB

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
ll n, m, k, a, b;
ll dista[maxn], distb[maxn];

vector<int>g[maxn];
set<int>edge[maxn];
vector<int>unsolved[maxn];

bool visiteda[maxn], visitedb[maxn];

void bfs() {
    for(int i=1;i<=n;i++) dista[i] = 1e9;
    queue<int>q;
    visiteda[k] = true;
    dista[k] = 0;
    q.push(k);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        for(int i:g[curr]) {
            if(!visiteda[i]) {
                visiteda[i] = true;
                dista[i] = dista[curr] + 1;
                q.push(i);
            }
        }
    }
}

void bfsb() {
    for(int i=1;i<=n;i++) {
        distb[i] = 1e9;
    }
    queue<int>q;
    visitedb[k] = true;
    distb[k] = 0;
    q.push(k);

    while(!q.empty()) {
        int curr = q.front(); q.pop();
        for(int i:g[curr]) {
            vector<int>temp;
            for(int j:unsolved[i]) {
                if(visitedb[j]) continue;
                temp.pb(j);
                if(edge[j].find(curr) != edge[j].end()) {
                    continue;
                }

                visitedb[j] = true;
                distb[j] = distb[curr] + 1;
                q.push(j);
            }
            unsolved[i] = temp;
        }
    }

}

int main() {
    cin>>n>>m>>k>>a>>b;

    int x, y;
    for(int i=0;i<m;i++) {
        cin>>x>>y;
        g[x].pb(y); g[y].pb(x);
        edge[x].insert(y); edge[y].insert(x);
        unsolved[x].pb(y); unsolved[y].pb(x);
    }

    bfs();
    bfsb();

    for(int i=1;i<=n;i++) {
        if(dista[i] % 2 == 0) {
            cout<<min(dista[i]*a, (dista[i]/2)*b)<<"\n";
        }
        else {
            ll cb = INT_MAX;
            if(visitedb[i]) cb = distb[i] * b;
            cout<<min(min(dista[i] * a, ((dista[i]-1)/2*b)+a),cb)<<"\n";
        }
    }
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	14 ms	9728 KB	Output is correct
4	Correct	13 ms	9728 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	13 ms	9856 KB	Output is correct
4	Correct	11 ms	9856 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	9856 KB	Output is correct
2	Correct	12 ms	9856 KB	Output is correct
3	Correct	11 ms	9828 KB	Output is correct
4	Correct	13 ms	9856 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	11936 KB	Output is correct
2	Correct	34 ms	11904 KB	Output is correct
3	Correct	48 ms	12408 KB	Output is correct
4	Correct	44 ms	12536 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	17184 KB	Output is correct
2	Correct	132 ms	17216 KB	Output is correct
3	Correct	133 ms	16120 KB	Output is correct
4	Correct	219 ms	18748 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	258 ms	22928 KB	Output is correct
2	Correct	234 ms	21212 KB	Output is correct
3	Correct	409 ms	24668 KB	Output is correct
4	Correct	403 ms	25220 KB	Output is correct
5	Correct	241 ms	23732 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	286 ms	25376 KB	Output is correct
2	Correct	238 ms	21752 KB	Output is correct
3	Correct	373 ms	25592 KB	Output is correct
4	Correct	394 ms	25180 KB	Output is correct
5	Correct	274 ms	25656 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	381 ms	28140 KB	Output is correct
2	Correct	376 ms	26356 KB	Output is correct
3	Correct	403 ms	26360 KB	Output is correct
4	Correct	434 ms	25168 KB	Output is correct
5	Correct	319 ms	27208 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	350 ms	27068 KB	Output is correct
2	Correct	419 ms	27124 KB	Output is correct
3	Correct	429 ms	26704 KB	Output is correct
4	Correct	402 ms	25080 KB	Output is correct
5	Correct	368 ms	28640 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	354 ms	27888 KB	Output is correct
2	Correct	331 ms	27744 KB	Output is correct
3	Correct	444 ms	27896 KB	Output is correct
4	Correct	471 ms	25208 KB	Output is correct
5	Correct	416 ms	28512 KB	Output is correct

Submission #102627

Compilation message