oj.uz

Submission #745982

# Submission time Handle Problem Language Result Execution time Memory
745982 2023-05-21T10:22:58 Z vjudge1 Cities (BOI16_cities) C++17
22 / 100
 202 ms 3480 KB 
#include <bits/stdc++.h>

using namespace std;

struct edge
{
    int dist,from,to;
    bool operator<(const edge x) const
    {
        return dist<x.dist;
    }
};

int n,k,m;
vector<int>parent;
vector<edge>edges;
vector<int>imp;

int holvan(int a) {
    return (parent[a]==a ? a : holvan(parent[a]));
}
void union_set(int a, int b) {

    parent[a]=b;
}
int main()
{
    cin>>n>>k>>m;
    edges.resize(m);
    imp.assign(k,0);
    for(int i=0;i<k;i++)
    {
        cin>>imp[i];
        imp[i]--;
    }
    for(int i=0;i<m;i++)
    {
        cin>>edges[i].from>>edges[i].to>>edges[i].dist;
        edges[i].from--;
        edges[i].to--;
    }
    long long mini=1e12;
    sort(edges.begin(),edges.end());
    for(int i=0;i<(1<<n);i++)
    {
        bool ok=true;
        for(int x:imp)
        {
            if(((1<<x)&i)==0)
            {
                ok=false;
            }
        }
        //cout << "proba " <<i << " " << ok <<endl;
        if(ok)
        {
            int sum_city=__builtin_popcount(i);
            int roads=0;
            long long sum=0;
            parent.assign(n,0);
            for(int i=0;i<n;i++)
            {
                parent[i]=i;
            }
            for(edge x:edges)
            {

                if(((1<<x.from)&i)!=0 && ((1<<x.to)&i)!=0)
                {
                    int a=x.from;
                    int b=x.to;
                    a=holvan(a), b=holvan(b);
                    //cout << a << " " << holvan(a) << " " << b << " " << holvan(b) << endl;
                    if(a!=b)
                    {
                        union_set(a, b);
                        //cout << "unio " << x.dist << "\n";
                        sum+=x.dist;
                        roads++;
                    }
                }
            }
            //cout << "mask: " << i << " " << sum << endl;
            if(sum_city==roads+1)
            {
                mini=min(mini,sum);
            }
        }
    }
    cout<<mini<<"\n";
    return 0;
}

/*

4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8

*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 58 ms 212 KB Output is correct
3 Correct 38 ms 212 KB Output is correct
4 Correct 22 ms 300 KB Output is correct
5 Correct 14 ms 296 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 202 ms 3264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 3324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 3480 KB Output isn't correct
2 Halted 0 ms 0 KB -