oj.uz

Submission #94620

# Submission time Handle Problem Language Result Execution time Memory
94620 2019-01-21T19:51:04 Z qoo2p5 Toll (APIO13_toll) C++17
100 / 100
 1414 ms 19604 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];
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;
	}
	p[u] = v;
	return 1;
}
 
void clr() {
	rep(i, 0, n + 1) {
		p[i] = i;
		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:16: 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:16: 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:130: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 7 ms 7544 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 9 ms 7644 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 9 ms 7644 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 10 ms 7672 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 9 ms 7644 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 10 ms 7672 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 164 ms 19604 KB Output is correct
8 Correct 196 ms 19572 KB Output is correct
9 Correct 176 ms 19440 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 9 ms 7644 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 10 ms 7672 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 164 ms 19604 KB Output is correct
8 Correct 196 ms 19572 KB Output is correct
9 Correct 176 ms 19440 KB Output is correct
10 Correct 1037 ms 19584 KB Output is correct
11 Correct 1414 ms 19444 KB Output is correct
12 Correct 1394 ms 19444 KB Output is correct