oj.uz

Submission #36256

# Submission time Handle Problem Language Result Execution time Memory
36256 2017-12-06T14:31:51 Z Flumen Price List (POI13_cen) C++11
100 / 100
 233 ms 14676 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int>node[100100],node1[100100],tmp;
int ans[100100],mark[100100];
queue<pair<int,int> >Q;
void bfs1(int k,int a,int b){
    Q.push(make_pair(k,0));
    while(!Q.empty()){
        mark[Q.front().first]=1;
        ans[Q.front().first]=min(b,2*a)*(Q.front().second/2)+a*(Q.front().second%2);
        for(int i=0;i<node[Q.front().first].size();i++){
            if(mark[node[Q.front().first][i]]==1)continue;
            mark[node[Q.front().first][i]]=1;
            Q.push(make_pair(node[Q.front().first][i],Q.front().second+1));
        }
        Q.pop();
    }
}
void bfs2(int k,int a,int b){
    int x,y,z;
    Q.push(make_pair(k,0));
    while(!Q.empty()){
        x=Q.front().first;
        y=Q.front().second;
        Q.pop();
        mark[x]=2;
        ans[x]=min(ans[x],min(y*b,y*2*a));
        for(int i=0;i<node1[x].size();i++){
            for(int j=0;j<node[node1[x][i]].size();j++){
                z=lower_bound(node1[node[node1[x][i]][j]].begin(),node1[node[node1[x][i]][j]].end(),x)-node1[node[node1[x][i]][j]].begin();
                if(mark[node[node1[x][i]][j]]==2)tmp.push_back(node[node1[x][i]][j]);
                else if(z<node1[node[node1[x][i]][j]].size()&&node1[node[node1[x][i]][j]][z]==x)tmp.push_back(node[node1[x][i]][j]);
                else{
                    mark[node[node1[x][i]][j]]=2;
                    Q.push(make_pair(node[node1[x][i]][j],y+1));
                }
            }
            node[node1[x][i]].clear();
            for(int j=0;j<tmp.size();j++){
                node[node1[x][i]].push_back(tmp[j]);
            }
            tmp.clear();
        }
    }
}
int main(){
    int n,m,k,a,b,i,x,y;
    scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        node[x].push_back(y);
        node[y].push_back(x);
        node1[x].push_back(y);
        node1[y].push_back(x);
    }
    for(i=1;i<=n;i++){
        sort(node[i].begin(),node[i].end());
        sort(node1[i].begin(),node1[i].end());
    }
    bfs1(k,a,b);
    bfs2(k,a,b);
    for(i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

Compilation message

cen.cpp: In function 'void bfs1(int, int, int)':
cen.cpp:11:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<node[Q.front().first].size();i++){
                      ^
cen.cpp: In function 'void bfs2(int, int, int)':
cen.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<node1[x].size();i++){
                      ^
cen.cpp:29:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<node[node1[x][i]].size();j++){
                          ^
cen.cpp:32:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 else if(z<node1[node[node1[x][i]][j]].size()&&node1[node[node1[x][i]][j]][z]==x)tmp.push_back(node[node1[x][i]][j]);
                          ^
cen.cpp:39:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<tmp.size();j++){
                          ^
cen.cpp: In function 'int main()':
cen.cpp:48:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
                                       ^
cen.cpp:51:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8292 KB Output is correct
2 Correct 9 ms 8292 KB Output is correct
3 Correct 19 ms 8284 KB Output is correct
4 Correct 16 ms 8284 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 10460 KB Output is correct
2 Correct 66 ms 10460 KB Output is correct
3 Correct 59 ms 9472 KB Output is correct
4 Correct 89 ms 10000 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12316 KB Output is correct
2 Correct 93 ms 11656 KB Output is correct
3 Correct 173 ms 12112 KB Output is correct
4 Correct 219 ms 11848 KB Output is correct
5 Correct 136 ms 12936 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 13344 KB Output is correct
2 Correct 109 ms 11716 KB Output is correct
3 Correct 186 ms 12244 KB Output is correct
4 Correct 169 ms 11848 KB Output is correct
5 Correct 139 ms 13720 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 14132 KB Output is correct
2 Correct 159 ms 13344 KB Output is correct
3 Correct 183 ms 12640 KB Output is correct
4 Correct 169 ms 11848 KB Output is correct
5 Correct 186 ms 14228 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 13588 KB Output is correct
2 Correct 169 ms 13588 KB Output is correct
3 Correct 233 ms 12904 KB Output is correct
4 Correct 193 ms 11848 KB Output is correct
5 Correct 159 ms 14676 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 13696 KB Output is correct
2 Correct 169 ms 13696 KB Output is correct
3 Correct 233 ms 13828 KB Output is correct
4 Correct 193 ms 11848 KB Output is correct
5 Correct 209 ms 14620 KB Output is correct