Submission #745912

#	Time	Username	Problem	Language	Result	Execution time	Memory
745912		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	1520 ms	7248 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const ll maxN = 2e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e12 + 7;

vector<pair<ll, pair<ll, ll> > > elek;
vector<ll> s, p;

ll holvan(ll a) {
    if(a == p[a]) return a;
    return p[a] = holvan(p[a]);
}

void unio(ll a, ll b) {
    a = holvan(a);
    b = holvan(b);

    if(a == b) return;
    if(s[a] < s[b]) swap(a, b);

    s[a] += s[b];
    p[b] = a;
}

ll n,k,m;

void resetdsu() {
    s.resize(n+1);
    p.resize(n+1);
    for(int i = 0; i < n; i++) {
        s[i] = 1;
        p[i] = i;
    }
}

vector<ll> fontos;

bool ok() {
    for(ll i = 0; i < fontos.size()-1; i++) {
        if(holvan(fontos[i]) != holvan(fontos[i+1])) return false;
    }
    return true;
}

int main() {

/*#ifndef ONLINE_JUDGE
   freopen("../../input.txt", "r", stdin);
   freopen("../../output.txt", "w", stdout);
#endif*/
   InTheNameOfGod;

    
    cin >> n >> k >> m;


    fontos.resize(k);
    for(ll &i : fontos) {
        cin >> i;
        i--;
    }

    for(ll i = 0; i < m; i++) {
        ll x,y,z;
        cin >> x >> y >> z;
        x--;
        y--;

        elek.push_back({z, {x, y}});
    }


    sort(elek.begin(), elek.end());
    ll must = 0;
    for(ll i : fontos) must += (1<<(i));

    ll mo = INF;

    for(ll mask = 0; mask < (1<<n); mask++) { // lehet javítani, ah lassú
        ll curmask = mask | must;

        set<ll> in;
        for(ll i = 0; i < n; i++) if((1<<i) & curmask) in.insert(i);
        resetdsu();


        ll cur = 0;
        for(auto el : elek) {
            ll x = el.second.first, y = el.second.second;
            if(holvan(x) == holvan(y) || in.find(x) == in.end() || in.find(y) == in.end()) continue;

            unio(x, y);
            cur += el.first;
        }

        mo = min(mo, cur);
        //cout << curmask << ": " << mo << endl;
    }

    cout << mo;

    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'bool ok()':
cities.cpp:43:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(ll i = 0; i < fontos.size()-1; i++) {
      |                   ~~^~~~~~~~~~~~~~~~~

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