Submission #961876

#	Time	Username	Problem	Language	Result	Execution time	Memory
961876		shezitt	Cities (BOI16_cities)	C++14	22 / 100	146 ms	604 KiB

cities

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

using ll = long long;

#define int ll
#define pb push_back
#define endl '\n'
#define fore(i, a, b) for(int i=a; i<b; ++i)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ii pair<int,int>

const int N = 21;

int n, k, m;
vector<ii> adj[N];
vector<int> important;

struct union_find {
    vector<int> pa;
    int n;
    union_find(int n) : n(n) {
        pa.assign(n, 0);
        iota(all(pa), 0);
    }
    int find(int x){
        if(x == pa[x]) return x;
        return pa[x] = find(pa[x]);
    }
    void join(int a, int b){
        a = find(a), b = find(b);
        pa[b] = a;
    }
};

struct edge {
    int u, v, c;
    bool operator<(const edge &otro){
        return c < otro.c;
    }
};

signed main(){  
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k >> m;
    important.resize(k);
    fore(i, 0, k){
        cin >> important[i];
        important[i]--;
    }

    vector<edge> edlist;

    fore(i, 0, m){
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        adj[u].pb(make_pair(v, c));
        adj[v].pb(make_pair(u, c));
        edlist.pb({u, v, c});
    }

    int ans = 4e18;

    for(int mask=0; mask<(1<<n); ++mask){

        bool sirve = 1;
        for(int x : important){
            if(((1<<x)&mask) == 0){
                sirve = 0;
                break;
            }
        }   
        if(sirve == 0) continue;

        vector<edge> curlist;

        for(auto [u, v, c] : edlist){
            if(((1 << u) & mask) == 0 or ((1 << v) & mask) == 0){
                continue;
            }
            curlist.pb({u, v, c});
        }

        sort(all(curlist));

        union_find dsu(n);

        int cur = 0;
        for(auto [u, v, c] : curlist){
            if(dsu.find(u) == dsu.find(v)) continue;
            dsu.join(u, v);
            cur += c;
        }

        bool ok = 1;
        for(int xx : important){
            ok &= dsu.find(xx) == dsu.find(important[0]);
        }

        if(ok){
            ans = min(ans, cur);
        }

    }

    cout << ans;

}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:86:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |         for(auto [u, v, c] : edlist){
      |                  ^
cities.cpp:98:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |         for(auto [u, v, c] : curlist){
      |                  ^

• Subtask 1: 22 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26