oj.uz

Submission #36255

# Submission time Handle Problem Language Result Execution time Memory
36255 2017-12-06T14:20:26 Z Flumen Price List (POI13_cen) C++11
10 / 100
 139 ms 8604 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int>node[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<node[x].size();i++){
            for(int j=0;j<node[node[x][i]].size();j++){
                z=lower_bound(node[node[node[x][i]][j]].begin(),node[node[node[x][i]][j]].end(),x)-node[node[node[x][i]][j]].begin();
                if(mark[node[node[x][i]][j]]==2)tmp.push_back(node[node[x][i]][j]);
                else if(z<node[node[node[x][i]][j]].size()&&node[node[node[x][i]][j]][z]==x)tmp.push_back(node[node[x][i]][j]);
                else{
                    mark[node[node[x][i]][j]]=2;
                    Q.push(make_pair(node[node[x][i]][j],y+1));
                }
            }
            node[node[x][i]].clear();
            for(int j=0;j<tmp.size();j++){
                node[node[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);
    }
    for(i=1;i<=n;i++){
        sort(node[i].begin(),node[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<node[x].size();i++){
                      ^
cen.cpp:29:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<node[node[x][i]].size();j++){
                          ^
cen.cpp:32:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 else if(z<node[node[node[x][i]][j]].size()&&node[node[node[x][i]][j]][z]==x)tmp.push_back(node[node[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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5148 KB Output is correct
2 Correct 0 ms 5148 KB Output is correct
3 Correct 0 ms 5148 KB Output is correct
4 Incorrect 0 ms 5148 KB Output isn't correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5148 KB Output is correct
2 Correct 3 ms 5148 KB Output is correct
3 Incorrect 0 ms 5148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5544 KB Output is correct
2 Correct 13 ms 5544 KB Output is correct
3 Incorrect 23 ms 5544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6732 KB Output is correct
2 Correct 33 ms 6732 KB Output is correct
3 Incorrect 46 ms 6072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7696 KB Output is correct
2 Correct 59 ms 7300 KB Output is correct
3 Incorrect 89 ms 7392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 8112 KB Output is correct
2 Correct 63 ms 7284 KB Output is correct
3 Incorrect 139 ms 7524 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 8604 KB Output is correct
2 Correct 86 ms 8080 KB Output is correct
3 Incorrect 136 ms 7788 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 8200 KB Output is correct
2 Correct 99 ms 8200 KB Output is correct
3 Incorrect 133 ms 7788 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 8316 KB Output is correct
2 Correct 119 ms 8184 KB Output is correct
3 Incorrect 139 ms 8316 KB Output isn't correct
4 Halted 0 ms 0 KB -