oj.uz

답안 #745940

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745940 2023-05-21T09:49:14 Z vjudge1 Cities (BOI16_cities) C++17
22 / 100
 1889 ms 7192 KB 
#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;
        }

        if(ok())mo = min(mo, cur);
    }

    cout << mo;

    return 0;
}

Compilation message

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
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1557 ms 304 KB Output is correct
3 Correct 1629 ms 296 KB Output is correct
4 Correct 1751 ms 300 KB Output is correct
5 Correct 1889 ms 308 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 110 ms 6960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 7068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 117 ms 7192 KB Output isn't correct
2 Halted 0 ms 0 KB -