oj.uz

Submission #39220

# Submission time Handle Problem Language Result Execution time Memory
39220 2018-01-10T07:49:10 Z qoo2p5 Toll (APIO13_toll) C++14
100 / 100
 1669 ms 33764 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
const ld EPS = (ld) 1e-7;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (int i = f; i < t; i++)
#define per(i, f, t) for (int i = f; i >= t; i--)

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
	x += y;
	if (x >= MOD) x -= MOD;
	if (x < 0) x += MOD;
}

ll mult(ll x, ll y) {
	return x * y % MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

const int N = (int) 3e5 + 123;

struct Edge {
	int u, v, c;
	
	bool operator<(const Edge &e) const {
		return c < e.c;
	}
};

int n, m, k;
ll amount[N], n_amount[N];
Edge e[N], my[N];
int id[N];
int p[N], rnk[N];
vector<pair<int, int>> g[N];

int get(int v) {
	return (p[v] == v ? v : (p[v] = get(p[v])));
}

bool unite(int u, int v) {
	u = get(u);
	v = get(v);
	if (u == v) {
		return 0;
	}
	if (rnk[u] > rnk[v]) {
		swap(u, v);
	} else if (rnk[u] == rnk[v]) {
		rnk[v]++;
	}
	p[u] = v;
	return 1;
}

void clr() {
	rep(i, 0, n + 1) {
		p[i] = i;
		rnk[i] = 0;
		g[i].clear();
	}
}

int depth[N];
int par[N], par_e[N];
int tin[N], tout[N];

void calc(int v, int f = -1) {
	if (v == -1) {
		depth[v] = 0;
	}
	par[v] = f;
	for (auto &e : g[v]) {
		int u = e.first;
		if (u == f) {
			continue;
		}
		if (e.second >= 0) {
			par_e[u] = e.second;
		} else {
			par_e[u] = -1;
		}
		depth[u] = depth[v] + 1;
		calc(u, v);
	}
}

bool taken[N];
ll mi[N];

ll cur;

ll dfs(int v, int f = -1) {
	ll res = amount[v];
	for (auto &e : g[v]) {
		int u = e.first;
		if (u == f) {
			continue;
		}
		int id = e.second;
		ll t = dfs(u, v);
		if (id >= 0) {
			cur += t * mi[id];
		}
		res += t;
	}
	return res;
}

void upd_up(int v, int w) {
	if (par_e[v] != -1) {
		mini(mi[par_e[v]], w);
	}
}

void run() {
	cin >> n >> m >> k;
	rep(i, 0, m) {
		cin >> e[i].u >> e[i].v >> e[i].c;
	}
	sort(e, e + m);
	rep(i, 0, k) {
		cin >> my[i].u >> my[i].v;
	}
	rep(i, 1, n + 1) {
		cin >> amount[i];
	}
	
	{
		clr();
		rep(i, 0, k) {
			unite(my[i].u, my[i].v);
		}
		vector<int> used;
		rep(i, 0, m) {
			if (unite(e[i].u, e[i].v)) {
				used.pb(i);
			}
		}
		
		clr();
		for (int i : used) {
			unite(e[i].u, e[i].v);
		}
		
		int ptr = 1;
		
		rep(i, 1, n + 1) {
			int v = get(i);
			if (!id[v]) {
				id[v] = ptr++;
			}
			id[i] = id[v];
			n_amount[id[v]] += amount[i];
		}
		
		n = ptr;
		
		copy(n_amount, n_amount + ptr, amount);
		rep(i, 0, k) {
			my[i].u = id[my[i].u];
			my[i].v = id[my[i].v];
		}
		
		map<pair<int, int>, int> edges;
		rep(i, 0, m) {
			int u = id[e[i].u];
			int v = id[e[i].v];
			if (u > v) {
				swap(u, v);
			}
			if (u == v) {
				continue;
			}
			
			if (edges.count({u, v})) mini(edges[{u, v}], e[i].c);
			else edges[{u, v}] = e[i].c;
		}
		
		ptr = 0;
		for (auto &it : edges) {
			e[ptr++] = {it.first.first, it.first.second, it.second};
		}
		m = ptr;
	}
	
	sort(e, e + m);
	
	{
		clr();
		vector<Edge> need;
		rep(i, 0, m) {
			if (unite(e[i].u, e[i].v)) {
				need.pb(e[i]);
			}
		}
		m = sz(need);
		rep(i, 0, m) {
			e[i] = need[i];
		}
	}
	
	ll ans = 0;
	assert(m <= k);
	
	rep(mask, 1, 1 << k) {
		clr();
		bool ok = 1;
		int cnt = 0;
		rep(i, 0, k) {
			if (mask & (1 << i)) {
				ok &= unite(my[i].u, my[i].v);
				g[my[i].u].pb({my[i].v, i});
				g[my[i].v].pb({my[i].u, i});
				cnt++;
			}
		}
		if (!ok) {
			continue;
		}
		
		fill(taken, taken + m, 0);
		rep(i, 0, m) {
			if (unite(e[i].u, e[i].v)) {
				g[e[i].u].pb({e[i].v, -1});
				g[e[i].v].pb({e[i].u, -1});
				taken[i] = 1;
			}
		}
		
		fill(mi, mi + k, LINF);
		calc(1);
		
		rep(i, 0, m) {
			if (!taken[i]) {
				int u = e[i].u;
				int v = e[i].v;
				if (depth[u] < depth[v]) swap(u, v);
				while (depth[u] > depth[v]) {
					upd_up(u, e[i].c);
					u = par[u];
				}
				while (u != v) {
					upd_up(u, e[i].c);
					upd_up(v, e[i].c);
					u = par[u];
					v = par[v];
				}
			}
		}
		
		cur = 0;
		dfs(1);
		maxi(ans, cur);
	}
	
	cout << ans << "\n";
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:72:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
                                        ^
toll.cpp:73:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".out", "w", stdout);
                                          ^
toll.cpp: In function 'void calc(int, int)':
toll.cpp:136:10: warning: array subscript is below array bounds [-Warray-bounds]
   depth[v] = 0;
          ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 32956 KB Output is correct
2 Correct 0 ms 32956 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 32956 KB Output is correct
2 Correct 0 ms 32956 KB Output is correct
3 Correct 0 ms 32956 KB Output is correct
4 Correct 0 ms 32956 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 32956 KB Output is correct
2 Correct 0 ms 32956 KB Output is correct
3 Correct 0 ms 32956 KB Output is correct
4 Correct 0 ms 32956 KB Output is correct
5 Correct 3 ms 32956 KB Output is correct
6 Correct 9 ms 32956 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 32956 KB Output is correct
2 Correct 0 ms 32956 KB Output is correct
3 Correct 0 ms 32956 KB Output is correct
4 Correct 0 ms 32956 KB Output is correct
5 Correct 3 ms 32956 KB Output is correct
6 Correct 9 ms 32956 KB Output is correct
7 Correct 169 ms 33764 KB Output is correct
8 Correct 183 ms 33764 KB Output is correct
9 Correct 169 ms 33764 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 32956 KB Output is correct
2 Correct 0 ms 32956 KB Output is correct
3 Correct 0 ms 32956 KB Output is correct
4 Correct 0 ms 32956 KB Output is correct
5 Correct 3 ms 32956 KB Output is correct
6 Correct 9 ms 32956 KB Output is correct
7 Correct 169 ms 33764 KB Output is correct
8 Correct 183 ms 33764 KB Output is correct
9 Correct 169 ms 33764 KB Output is correct
10 Correct 1106 ms 33764 KB Output is correct
11 Correct 1649 ms 33764 KB Output is correct
12 Correct 1669 ms 33764 KB Output is correct