Submission #335019

#	Time	Username	Problem	Language	Result	Execution time	Memory
335019		limabeans	Cities (BOI16_cities)	C++17	22 / 100	198 ms	41556 KiB

cities

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;

struct dsu0 {
    vector<int> par, siz;
    int n;
    int cc;
    int largest;
    void init(int n) {
	assert(n>0);
	this->n=n;
	cc=n;
	par.resize(n+10);siz.resize(n+10);
	for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
	largest=1;
    }
    int parent(int x) {
	assert(x>=0 && x<n);
	return par[x]==x?x:par[x]=parent(par[x]);
    }
    bool join(int x, int y) {
	x=parent(x);y=parent(y);
	if (x==y) return false;
	cc--;
	if (siz[x]<siz[y]) swap(x,y);
	siz[x]+=siz[y];par[y]=x;
	largest=max(largest,siz[x]);
	return true;
    }
};


int n,m,k;
vector<pair<ll,int>> g[maxn];
bool imp[maxn];
vector<pair<ll,pair<int,int>>> edges;
vector<int> a;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k>>m;
    for (int i=0; i<k; i++) {
	int x;
	cin>>x; --x;
	imp[x]=true;
	a.push_back(x);
    }
    for (int i=0; i<m; i++) {
	int u,v,w; cin>>u>>v>>w;
	--u; --v;
	edges.push_back({w,{u,v}});
	g[u].push_back({w,v});
	g[v].push_back({w,u});
    }

    sort(edges.begin(),edges.end());

    ll res = 1e18;

    for (int mask=1; mask<1<<n; mask++) {
	bool ok = true;
	for (int j=0; j<n && ok; j++) {
	    if (imp[j] && (mask>>j&1)==0) ok=false;
	}

	if (ok) {
	    dsu0 dsu;
	    dsu.init(n);

	    ll cur = 0;
	    for (auto ed: edges) {
		int u = ed.second.first;
		int v = ed.second.second;
		if ((mask>>u&1) && (mask>>v&1)) {
		    if (dsu.join(u,v)) {
			cur += ed.first;
		    }
		}
	    }

	    int p = dsu.parent(a[0]);
	    for (int x: a) {
		if (p!=dsu.parent(x)) ok = false;
	    }

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


    cout<<res<<endl;    
    return 0;
}

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