Submission #1166069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166069		tkm_algorithms	Toll (APIO13_toll)	C++20	0 / 100	2 ms	4932 KiB

toll

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
	
#define all(x) begin(x), end(x)
#define edgew tuple<int, int, int> 
#define edge tuple<int, int>
//#define sz(x) (int)(x).size()

typedef long long ll;
#define int ll

const char nl = '\n';
const int N = 1e5+5;

struct connectivity{
    vector<int> ata;
    vector<int> sz;
    int n;
    connectivity(int _n){
        n = _n;
        ata.resize(n+1);
        sz.resize(n+1);
    }
    void init(){
        for (int i = 1; i <= n; i++)
            ata[i] = i, sz[i] = 1;
    }
    int tap(int x){
        if (ata[x] == x)
            return x;
        return ata[x] = tap(ata[x]);
    }
    bool merge(int x, int y){
        if ((x=tap(x)) == (y=tap(y)))
            return 0;
        if (sz[x] < sz[y])
            swap(x, y);
        ata[y] = x;
        sz[x] += sz[y];
        return 1;
    }
    bool is_connected(int x, int y){
        return tap(x) == tap(y);
    }
    vector<int> get_components(){
        vector<int> components;
        for (int i = 1; i <= n; i++)
            if (ata[i] == i)
                components.push_back(i);
        return components;
    }
};

vector<edge> re[N];
pair<int, int> par[N];
int lvl[N];

void dfs(int a, int p, int m) {
	par[a] = {p, m};
	for (auto [i, w]: re[a]) {
		if (i == p)continue;
		lvl[i] = lvl[a] + 1;
		dfs(i, a, max(m, w));
	}
}

int mx(int a, int b) {
	int ans = 0;
	while (a != b) {
		if (lvl[a] < lvl[b])swap(a, b);
		ans = max(ans, par[a].second);
		a = par[a].first;
		//cout << a << " " << b << nl;
	}
	
	return ans;
}

vector<tuple<int, int, int>> ans[N]; // kuda, sena, can
int arr[N];
int res = 0;

int jog (int u, int p, int w, int can) {
	//
	int sm = arr[u]; //?
	for (auto [b, c, d]: ans[u]) {
		if (b == p)continue;
		sm += jog(b, u, c, d);
	}
	
	res += sm*w*can;
	return sm;
}

bool cmp(tuple<int, int, int, int> &A, tuple<int, int, int, int> &B) {
	int a, b, c, d;
	tie(a, b, c, d) = A;
	
	int x, y, z, bl;
	tie(x, y, z, bl) = B;
	 
	if (a != x)return a < x;
	if (d == 1)return 1;
	else return 0; // 1 if its blue
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

	int n, m, k; cin >> n >> m >> k;
	
	//connectivity dsu;
	connectivity dsu(n+1);
	dsu.init();
	
	vector<edgew> g;
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		g.push_back({c, a, b});
	}
	
	sort(all(g));
	
	//for (auto [c, a, b]: g)cout << c << " " << a << " " << b << nl;
	
	vector<tuple<int, int, int, int>> sonky;
	for (auto [c, a, b]: g) {
		if (dsu.merge(a, b)){re[a].push_back({b, c}), re[b].push_back({a, c}); sonky.push_back({c, a, b, 0}); }
	}
	
	dfs(1, 1, 0);
	
	//cout << lvl[1] << " " << lvl[3];
	for (int i = 0; i < k; ++i) {
		int a, b; cin >> a >> b;
		int M = mx(a, b);
		sonky.push_back({M, a, b, 1});
	}
	
	for (int i = 1; i <= n; ++i)cin >> arr[i];
	
	sort(all(sonky), cmp);
	dsu.init();
	
	for (auto [c, a, b, d]: sonky) {
		if (dsu.merge(a, b))ans[a].push_back({b, c, d}), ans[b].push_back({a, c, d});
	}
	
	jog(1, 1, 0, 0);
	cout << res;
	return 0;
}

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