Submission #506447

#	Time	Username	Problem	Language	Result	Execution time	Memory
506447		pokmui9909	Toll (APIO13_toll)	C++14	0 / 100	2 ms	4940 KiB

toll

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

#define x first
#define y second
class UnionFind{
public:
	UnionFind(ll S){
		p.resize(S + 5, -1);
	}
	ll Find(ll n){
		if (p[n] < 0) return n;
		else return p[n] = Find(p[n]);
	}
	void Union(ll a, ll b){
		a = Find(a), b = Find(b);
		if (a == b) return;
		p[b] += p[a];
        p[a] = b;
    }
	bool Same(ll a, ll b) { return Find(a) == Find(b); }
private:
	vector<ll> p;
};
ll N, M, K;
vector<vector<pair<ll, ll>>> T(100005);
struct Edge{
    ll u, v, c;
    bool operator<(const Edge &r)const{
        return c < r.c;
    }
};
vector<Edge> E;
vector<pair<ll, ll>> add;
ll P[100005];
ll Size[100005];
struct MyStruct{
    ll n, c, f;
};
vector<vector<MyStruct>> G(100005);
ll sum = 0, ans = 0;
void dfs(ll u, ll p){
    Size[u] = P[u];
    for(auto i : G[u]){
        ll v = i.n, c = i.c, f = i.f;
        if(v == p) continue;
        dfs(v, u);
        Size[u] += Size[v];
        sum += f * c * Size[v];
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);
 
    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        ll u, v, c; cin >> u >> v >> c;
        T[u].push_back({v, c});
        T[v].push_back({u, c});
        E.push_back({u, v, c});
    }
    sort(E.begin(), E.end());
    for(int i = 1; i <= K; i++){
        ll u, v; cin >> u >> v;
        add.push_back({u, v});
    }
    for(int i = 1; i <= N; i++){
        cin >> P[i];
    }
    for(int i = 0; i < (1 << K); i++){
        for(int j = 1; j <= N; j++){
            Size[j] = 0;
            G[j].clear();
        }
        UnionFind uf(N);
        ll ok = 1;
        vector<Edge> V;
        for(int j = 0; j < K; j++){
            if(i & (1 << j)){
                ll u = add[j].x, v = add[j].y;
                if(uf.Same(u, v)){
                    ok = 0;
                    break;
                } else {
                    uf.Union(u, v);
                    V.push_back({u, v, 0});
                }
            }
        }
        if(!ok) continue;
        vector<Edge> MST;
        ll MinCost = 1e18;
        for(int j = 0; j < M; j++){
            ll u = E[j].u, v = E[j].v, c = E[j].c;
            if(!uf.Same(u, v)){
                uf.Union(u, v);
                MST.push_back({u, v, c});
            } else {
                MinCost = min(MinCost, c);
            }
        }
        for(int j = 0; j < V.size(); j++){
            ll u = V[j].u, v = V[j].v, c = MinCost;
            G[u].push_back({v, c, 1});
            G[v].push_back({u, c, 1});
        }
        for(int j = 0; j < MST.size(); j++){
            ll u = MST[j].u, v = MST[j].v, c = MST[j].c;
            G[u].push_back({v, c, 0});
            G[v].push_back({u, c, 0});
        }
        sum = 0;
        dfs(1, -1);
        ans = max(ans, sum);
    }
    cout << ans;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int j = 0; j < V.size(); j++){
      |                        ~~^~~~~~~~~~
toll.cpp:109:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int j = 0; j < MST.size(); j++){
      |                        ~~^~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22