oj.uz

Submission #27716

# Submission time Handle Problem Language Result Execution time Memory
27716 2017-07-13T14:06:58 Z top34051 Cities (BOI16_cities) C++14
74 / 100
 4000 ms 44952 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define inf (long long)1e16
int n,k,m;
int p2[10];
int sp[maxn];
int sz[maxn];
int szcan[35];
long long mem[maxn][35];
vector<pair<int,int> > can[35];
vector<pair<int,int> > from[maxn];
priority_queue<pair<long long,int> > heap;
void mssp(int bit) {
    int i,x,y;
    long long val;
    for(i=1;i<=n;i++) heap.push({-mem[i][bit],i});
    while(!heap.empty()) {
        x = heap.top().second; val = -heap.top().first; heap.pop();
        if(val>mem[x][bit]) continue ;
        for(i=0;i<sz[x];i++) {
            y = from[x][i].first; val = from[x][i].second;
            if(mem[y][bit] > mem[x][bit] + val) {
                mem[y][bit] = mem[x][bit] + val;
                heap.push({-mem[y][bit],y});
            }
        }
    }
}
main() {
    int i,j,x,y,val,bit;
    long long ans;
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n;i++) sp[i] = -1;
    for(i=0;i<k;i++) scanf("%d",&x), sp[x] = i;
    while(m--) {
        scanf("%d%d%d",&x,&y,&val);
        from[x].push_back({y,val}); from[y].push_back({x,val});
    }
    p2[-1] = 0; p2[0] = 1;
    for(i=1;i<=k;i++) p2[i] = p2[i-1]*2;
    for(i=0;i<p2[k];i++) {
        for(j=0;j<p2[k];j++) if(((i&j)==j) && i>=j) can[i].push_back({j,i-j});
        szcan[i] = can[i].size();
    }
    for(x=1;x<=n;x++) {
        sz[x] = from[x].size();
        for(bit=0;bit<p2[k];bit++) mem[x][bit] = inf;
        mem[x][p2[sp[x]]] = 0;
    }
    for(bit=0;bit<p2[k];bit++) {
        for(x=1;x<=n;x++) for(i=0;i<szcan[bit];i++) mem[x][bit] = min(mem[x][bit],mem[x][can[bit][i].first] + mem[x][can[bit][i].second]);
        if(bit < p2[k]-1) mssp(bit);
    }
    ans = inf;
    for(i=1;i<=n;i++) ans = min(ans,mem[i][p2[k]-1]);
    printf("%lld",ans);
}

Compilation message

cities.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cities.cpp: In function 'int main()':
cities.cpp:33:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&k,&m);
                             ^
cities.cpp:35:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=0;i<k;i++) scanf("%d",&x), sp[x] = i;
                                               ^
cities.cpp:37:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&x,&y,&val);
                                   ^
cities.cpp:40:10: warning: array subscript is below array bounds [-Warray-bounds]
     p2[-1] = 0; p2[0] = 1;
          ^

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 44952 KB Output is correct
2 Correct 896 ms 44880 KB Output is correct
3 Correct 593 ms 38776 KB Output is correct
4 Correct 99 ms 37036 KB Output is correct
5 Correct 476 ms 44944 KB Output is correct
6 Correct 93 ms 37124 KB Output is correct
7 Correct 3 ms 32628 KB Output is correct
8 Correct 3 ms 32628 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32628 KB Output is correct
2 Correct 6 ms 32628 KB Output is correct
3 Correct 6 ms 32636 KB Output is correct
4 Correct 3 ms 32628 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1903 ms 44944 KB Output is correct
2 Correct 1793 ms 44736 KB Output is correct
3 Correct 1399 ms 38780 KB Output is correct
4 Correct 899 ms 41380 KB Output is correct
5 Correct 309 ms 39296 KB Output is correct
6 Correct 166 ms 38788 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3469 ms 44948 KB Output is correct
2 Execution timed out 4000 ms 44944 KB Execution timed out
3 Halted 0 ms 0 KB -