Submission #1245819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245819		vtrung	Cities (BOI16_cities)	C++20	0 / 100	79 ms	34888 KiB

cities

#include <bits/stdc++.h>
using namespace std; 
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fi first
#define se second
#define mll map<ll, ll>
#define sll set<ll>
const ll du = 1e9 + 7;
const ll ars = 1e6 + 5;

int n, m, k;
int c[ars], num[ars];
int d[ars], a[ars];
vector<pll> adj[ars];
bool vs[ars];
struct edge{
    ll u, v, w;
};
bool cmp(edge a, edge b){
    return a.w < b.w;
}
edge e[ars];
int timcha(int a){
    while(a != c[a]) a = c[a];
    return a;
}
bool dsu(int x, int y){
    x = timcha(x);
    y = timcha(y);
    if(x == y) return false;
    if(num[x] > num[y]) swap(x, y);
    c[x] = y;
    num[y] += num[x];
    return true;
}
void mst(){
    for(int i = 1; i <= n; i++){
        num[i] = 1;
        c[i] = i;
    }
    sort(e + 1, e + 1 + m, cmp);
    int dem = 0;
    for(int i = 1;i <= m; i++){
        if(dem == (n - 1)) break;
        bool fl = dsu(e[i].u, e[i].v);
        if(!fl) continue;
        adj[e[i].u].pb({e[i].v, e[i].w});
        adj[e[i].v].pb({e[i].u, e[i].w});
        dem++;
    }
}
ll ans = 0;
void dfs(int u, int p){
    for(auto[v, s] : adj[u]){
        if(v == p) continue;
        //cout << u << " " << v << " " << s << '\n';
        dfs(v, u);
        if(d[v] < k && d[v] > 0) ans += s;
        d[u] += d[v];
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n >> k >> m;
    for(int i = 1; i <= k; i++) cin >> a[i];
    for(int i = 1; i <= m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    mst();
    for(int i = 1; i <= k; i++) d[a[i]]++;
    dfs(1, 0);
    cout << ans;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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