oj.uz

Submission #27467

# Submission time Handle Problem Language Result Execution time Memory
27467 2017-07-13T05:49:15 Z top34051 Cities (BOI16_cities) C++14
51 / 100
 4000 ms 235020 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define inf (long long)1e16
struct node {
    int x,bit;
    long long val;
    node(int _x = 0,int _bit = 0,long long _val = 0) {
        x = _x; bit = _bit; val = _val;
    }
    bool operator < (node a) const {
        return a.val<val;
    }
};
int n,k,m;
int p2[10];
int sp[maxn];
long long mem[maxn][35];
vector<pair<int,int> > from[maxn];
priority_queue<node> heap;
main() {
    int i,x,y,val,bit;
    node t;
    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(x=1;x<=n;x++) {
        for(bit=0;bit<p2[k];bit++) mem[x][bit] = inf;
        if(sp[x]!=-1) {
            mem[x][p2[sp[x]]] = 0;
            heap.push(node(x,p2[sp[x]],0));
        }
    }
    while(!heap.empty()) {
        t = heap.top(); heap.pop();
        if(t.bit==p2[k]-1) {
            printf("%lld",t.val);
            return 0;
        }
        for(bit=0;bit<p2[k];bit++) {
            if(mem[t.x][t.bit|bit] > mem[t.x][t.bit] + mem[t.x][bit]) {
                mem[t.x][t.bit|bit] = mem[t.x][t.bit] + mem[t.x][bit];
                heap.push(node(t.x,t.bit|bit,mem[t.x][t.bit|bit]));
            }
        }
        for(i=0;i<from[t.x].size();i++) {
            y = from[t.x][i].first; val = from[t.x][i].second;
            if(mem[y][t.bit|p2[sp[y]]] > mem[t.x][t.bit] + val) {
                mem[y][t.bit|p2[sp[y]]] = mem[t.x][t.bit] + val;
                heap.push(node(y,t.bit|p2[sp[y]],mem[y][t.bit|p2[sp[y]]]));
            }
        }
    }
}

Compilation message

cities.cpp:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cities.cpp: In function 'int main()':
cities.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<from[t.x].size();i++) {
                  ^
cities.cpp:24: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:26: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:28: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:31: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 32104 KB Output is correct
2 Correct 0 ms 32104 KB Output is correct
3 Correct 0 ms 32104 KB Output is correct
4 Correct 0 ms 32104 KB Output is correct
5 Correct 0 ms 32104 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 62992 KB Output is correct
2 Correct 973 ms 50632 KB Output is correct
3 Correct 126 ms 36848 KB Output is correct
4 Correct 123 ms 37300 KB Output is correct
5 Correct 403 ms 44552 KB Output is correct
6 Correct 116 ms 36936 KB Output is correct
7 Correct 3 ms 32372 KB Output is correct
8 Correct 0 ms 32236 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33020 KB Output is correct
2 Correct 6 ms 32628 KB Output is correct
3 Correct 0 ms 32244 KB Output is correct
4 Correct 6 ms 32628 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 87560 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 235020 KB Execution timed out
2 Halted 0 ms 0 KB -