oj.uz

Submission #26258

# Submission time Handle Problem Language Result Execution time Memory
26258 2017-06-28T15:27:45 Z sgtlaugh Cities (BOI16_cities) C++14
100 / 100
 2756 ms 43876 KB 
#include <stdio.h>
#include <bits/stdtr1c++.h>

#define MAXK 5
#define MAXN 100010
#define clr(ar) memset(ar, 0, sizeof(ar))
#define read() freopen("lol.txt", "r", stdin)
#define dbg(x) cout << #x << " = " << x << endl
#define ran(a, b) ((((rand() << 15) ^ rand()) % ((b) - (a) + 1)) + (a))

using namespace std;

const long long INF = 1LL << 60;

bitset <MAXN> visited;
int n, k, m, special[MAXK];
long long dis[1 << MAXK][MAXN];
vector <pair<int, int> > graph[MAXN];

void dijkstra(long long dis[MAXN]){
    int i, j, v, w;
    priority_queue <pair<long long, int> > PQ;
    for (i = 1; i <= n; i++){
        visited[i] = 0;
        if (dis[i] < INF) PQ.push(make_pair(-dis[i], i));
    }

    while (!PQ.empty()){
        pair <long long, int> cur = PQ.top();
        PQ.pop();
        if (!visited[cur.second] && -cur.first == dis[cur.second]){
            i = cur.second, visited[i] = 1;
            for (j = 0; j < graph[i].size(); j++){
                v = graph[i][j].first, w = graph[i][j].second;
                if (dis[v] >  dis[i] + w){
                    dis[v] = dis[i] + w;
                    PQ.push(make_pair(-dis[v], v));
                }
            }
        }
    }
}

long long minimumSteinerTree(){
    int i, j, mask, submask;

    for (mask = 1; mask < (1 << k); mask++){
        for (i = 1; i <= n; i++) dis[mask][i] = INF;
        if (__builtin_popcount(mask) == 1){
            dis[mask][special[31 - __builtin_clz(mask)]] = 0;
        }
        else{
            for (i = 1; i <= n; i++){
                for (submask = mask - 1; submask >= (submask ^ mask); submask = (submask - 1) & mask){
                    dis[mask][i] = min(dis[mask][i], dis[submask][i] + dis[submask ^ mask][i]);
                }
            }
        }
        dijkstra(dis[mask]);
    }

    return *std::min_element(dis[mask - 1] + 1, dis[mask - 1] + 1 + n);
}

int main(){
    int i, j, u, v, w;

    while (scanf("%d %d %d", &n, &k, &m) != EOF){
        for (i = 0; i < MAXN; i++) graph[i].clear();
        for (i = 0; i < k; i++) scanf("%d", &special[i]);

        for (i = 0; i < m; i++){
            scanf("%d %d %d", &u, &v, &w);
            graph[u].push_back(make_pair(v, w));
            graph[v].push_back(make_pair(u, w));
        }

        printf("%lld\n", minimumSteinerTree());
    }
    return 0;
}

Compilation message

cities.cpp: In function 'void dijkstra(long long int*)':
cities.cpp:33:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < graph[i].size(); j++){
                           ^
cities.cpp: In function 'long long int minimumSteinerTree()':
cities.cpp:45:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, mask, submask;
            ^
cities.cpp: In function 'int main()':
cities.cpp:66:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, u, v, w;
            ^
cities.cpp:70:57: 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", &special[i]);
                                                         ^
cities.cpp:73:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", &u, &v, &w);
                                          ^

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 43876 KB Output is correct
2 Correct 686 ms 43808 KB Output is correct
3 Correct 429 ms 36676 KB Output is correct
4 Correct 96 ms 34048 KB Output is correct
5 Correct 266 ms 41828 KB Output is correct
6 Correct 79 ms 34068 KB Output is correct
7 Correct 3 ms 29512 KB Output is correct
8 Correct 3 ms 29512 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29512 KB Output is correct
2 Correct 9 ms 29512 KB Output is correct
3 Correct 3 ms 29520 KB Output is correct
4 Correct 3 ms 29512 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1413 ms 43868 KB Output is correct
2 Correct 1389 ms 43664 KB Output is correct
3 Correct 973 ms 36680 KB Output is correct
4 Correct 763 ms 39284 KB Output is correct
5 Correct 193 ms 35656 KB Output is correct
6 Correct 133 ms 35672 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2713 ms 43872 KB Output is correct
2 Correct 2756 ms 43864 KB Output is correct
3 Correct 2576 ms 43712 KB Output is correct
4 Correct 1579 ms 36680 KB Output is correct
5 Correct 1493 ms 39284 KB Output is correct
6 Correct 303 ms 35640 KB Output is correct
7 Correct 159 ms 35536 KB Output is correct