oj.uz

Submission #879740

# Submission time Handle Problem Language Result Execution time Memory
879740 2023-11-28T03:43:52 Z marvinthang Toll (APIO13_toll) C++17
100 / 100
 1608 ms 11640 KB 
/*************************************
*    author: marvinthang             *
*    created: 28.11.2023 09:58:49    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// index from 0 to n
struct DisjointSet {
    vector <int> par;
    DisjointSet(int n = 0): par(n + 1, -1) {}
    void reset(void) { fill(par.begin(), par.end(), -1); }
    void resize(int n) { par.assign(n + 1, -1); }
    bool connected(int u, int v) { return find(u) == find(v); }
    bool isRoot(int u) { return par[u] < 0; }
    int size(int u) { return -par[find(u)]; }
    int find(int u) { return par[u] < 0 ? u : par[u] = find(par[u]); }
    bool join(int u, int v) {
        if ((u = find(u)) == (v = find(v))) return false;
        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v]; par[v] = u;
        return true;
    }
};
using DSU = DisjointSet;

// end of template

void process(void) {
	int n, m, k; cin >> n >> m >> k;
	vector <array <int, 3>> edges(m + k);
	FOR(i, k, m + k) cin >> edges[i][1] >> edges[i][2] >> edges[i][0];
	REP(i, k) REP(j, 2) cin >> edges[i][j + 1];
	vector <int> p(n); cin >> p;
	sort(k + ALL(edges));
	DSU dsu(n);
	vector <bool> on_mst(m + k);
	REP(i, m + k) {
		REP(j, 2) --edges[i][j + 1];
		on_mst[i] = dsu.join(edges[i][1], edges[i][2]);
	}
	dsu.reset();
	FOR(i, k, m + k) if (on_mst[i]) dsu.join(edges[i][1], edges[i][2]);
	vector <int> id(n, -1);
	int sz = 0;
	REP(i, n) {
		int p = dsu.find(i);
		if (id[p] < 0) id[p] = sz++;
		id[i] = id[p];
	}
	vector <long long> cnt(sz);
	REP(i, n) cnt[id[i]] += p[i];
	vector <array <int, 3>> imp_edges;
	int ne = k;
	FOR(i, k, m + k) if (!on_mst[i] && dsu.join(edges[i][1], edges[i][2])) edges[ne++] = edges[i];
	REP(i, ne) edges[i][1] = id[edges[i][1]], edges[i][2] = id[edges[i][2]];
	dsu.resize(sz);
	vector <vector <int>> adj(sz);
	vector <int> depth(sz), par(sz), mi(sz);
	vector <long long> tree_size(sz);
	auto solve = [&] (int mask) {
		REP(i, sz) {
			adj[i].clear();
			depth[i] = par[i] = 0;
			mi[i] = (int) 1e6;
		}
		dsu.reset();
		REP(i, k) if (BIT(mask, i)) {
			int u = edges[i][1], v = edges[i][2];
			if (!dsu.join(u, v)) return 0LL;
			adj[u].push_back(i);
			adj[v].push_back(i);
		}
		vector <int> rem_edge;
		FOR(i, k, ne) {
			int u = edges[i][1], v = edges[i][2];
			if (dsu.join(u, v)) {
				adj[u].push_back(i);
				adj[v].push_back(i);
			} else rem_edge.push_back(i);
		}
		function<void(int)> dfs = [&] (int u) {
			tree_size[u] = cnt[u];
			for (int i: adj[u]) {
				int v = edges[i][1] ^ edges[i][2] ^ u;
				if (v != par[u]) {
					par[v] = u;
					depth[v] = depth[u] + 1;
					dfs(v);
					tree_size[u] += tree_size[v];
				}
			}
		};
		dfs(0);
		for (int i: rem_edge) {
			int u = edges[i][1], v = edges[i][2], w = edges[i][0];
			while (u != v) {
				if (depth[u] < depth[v]) swap(u, v);
				mi[u] = min(mi[u], w);
				u = par[u];
			}
		}
		long long cur = 0;
		function <void(int)> dfs2 = [&] (int u) {
			for (int i: adj[u]) {
				int v = edges[i][1] ^ edges[i][2] ^ u;
				if (v != par[u]) {
					if (i < k) cur += mi[v] * tree_size[v];
					dfs2(v);
				}
			}
		};
		dfs2(0);
		return cur;
	};
	long long res = 0;
	FOR(mask, 1, MASK(k)) res = max(res, solve(mask));
	cout << res << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("toll");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:158:2: note: in expansion of macro 'file'
  158 |  file("toll");
      |  ^~~~
toll.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:158:2: note: in expansion of macro 'file'
  158 |  file("toll");
      |  ^~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 125 ms 11604 KB Output is correct
8 Correct 135 ms 11400 KB Output is correct
9 Correct 132 ms 11492 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 125 ms 11604 KB Output is correct
8 Correct 135 ms 11400 KB Output is correct
9 Correct 132 ms 11492 KB Output is correct
10 Correct 1097 ms 11640 KB Output is correct
11 Correct 1586 ms 11632 KB Output is correct
12 Correct 1608 ms 11632 KB Output is correct