oj.uz

Submission #441692

# Submission time Handle Problem Language Result Execution time Memory
441692 2021-07-05T20:18:19 Z AriaH Toll (APIO13_toll) C++17
78 / 100
 2500 ms 37688 KB 
/** work as hard as you can and keep the first place **/

#pragma GCC optimize("O2")
#include<bits/stdc++.h>

using namespace std;

typedef long long			ll;
typedef long double			ld;
typedef pair < int, int > 	pii;
typedef pair < ll, ll > 	pll;

#define F					first
#define S					second
#define all(x)				x.begin(), x.end()
#define SZ(x)				(int)x.size()
#define Mp					make_pair

const int N = 3e5 + 50;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;

ll pw(ll a, ll b, ll M = mod, ll ret = 1) { while(b) { ret = ret * (b & 1? a : 1) % M, a = a * a % M, b >>= 1; } return ret; }

ll tot, ret, ted[N], sub[N], Size[N];

int n, m, k, ptr, ROOT, sz[N], V[N], U[N], C[N], par[N], ord[N], in1[N], in2[N], T[N], query[N], St[N], Fi[N];

vector < int > vec, roots, G[N];

inline void init() { for(int i = 1; i <= n; i ++) sz[i] = 1, par[i] = i, ted[i] = T[i]; }

int get(int x) { return (x == par[x]? x : par[x] = get(par[x])); }

bool unify(int v, int u)
{
	v = get(v), u = get(u);
	if(v == u) return 0;
	par[u] = v;
	ted[v] += ted[u];
	return 1;
}

bool cmp(int i, int j)
{
	return C[i] < C[j];
}

set < pii > st[N];

void pre(int v, int last = 0)
{
	St[v] = ++ptr;
	for(auto id : G[v])
	{
		if(id == last) continue;
		int u = V[id] ^ U[id] ^ v;
		pre(u, id);
	}
	Fi[v] = ptr;
	///printf("v = %d St = %d Fi = %d\n", v, St[v], Fi[v]);
}

void dfs(int v, int last = 0)
{
	sub[v] = Size[v];
	for(auto id : G[v])
	{
		if(id == last) continue;
		int u = V[id] ^ U[id] ^ v;
		dfs(u, id);
		if(SZ(st[v]) < SZ(st[u])) st[v].swap(st[u]);
		for(auto now : st[u])
		{
			int node = now.S;
			if(!(St[v] <= St[node] && Fi[node] <= Fi[v]))
			{
				st[v].insert(now);
			}
		}
		sub[v] += sub[u];
	}
	pii cu = *st[v].begin();
	while(St[v] <= St[cu.S] && Fi[cu.S] <= Fi[v])
	{
		st[v].erase(cu);
		cu = *st[v].begin();
	}
	if(last > m)
	{	
		ret += 1ll * cu.F * sub[v];
	}
}

void solve(int mask)
{
	///printf("mask = %d\n", mask);
	ptr = 0;
	ret = 0;
	for(auto v : roots) sz[v] = 1, G[v].clear(), par[v] = v, ted[v] = 0, st[v].clear();
	for(int i = m + 1; i <= m + k; i ++)
	{
		int id = i - m - 1;
		if(mask >> id & 1)
		{
			G[V[i]].push_back(i);
			G[U[i]].push_back(i);
			///printf("E = %d\n", i);
			if(!unify(V[i], U[i]))
			{
			    ///printf("0\n");
			    return;
			}
		}
	}
	for(auto i : vec)
	{
		///printf("%d %d\n", V[i], U[i]);
		if(V[i] == U[i]) continue;
		if(unify(V[i], U[i]))
		{
			G[V[i]].push_back(i);
			G[U[i]].push_back(i);
			///printf("E = %d\n", i);
		}
		else
		{
			st[V[i]].insert({C[i], U[i]});
			st[U[i]].insert({C[i], V[i]});
		}
	}
	pre(ROOT);
	dfs(ROOT);
	tot = max(tot, ret);
	///printf("%lld\n", ret);
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; i ++)
	{
		scanf("%d%d%d", &V[i], &U[i], &C[i]);
		ord[i] = i;
	}
	sort(ord + 1, ord + m + 1, cmp);
	init();
	for(int j = 1; j <= m; j ++)	
	{
		int i = ord[j];
		in1[i] = unify(V[i], U[i]);
	}
	init();
	for(int i = m + 1; i <= m + k; i ++)
	{
		scanf("%d%d", &V[i], &U[i]);
		unify(V[i], U[i]);
	}
	for(int i = 1; i <= n; i ++) { scanf("%d", &T[i]); }
	for(int j = 1; j <= m; j ++)
	{
		int i = ord[j];
		in2[i] = unify(V[i], U[i]);
	}
	init();
	for(int i = 1; i <= m; i ++)
	{
		if(in1[i] > in2[i])
		{
			vec.push_back(i);
		}
		if(in2[i])
		{
			unify(V[i], U[i]);
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		roots.push_back(get(i));
	}
	sort(all(roots));
	roots.resize(unique(all(roots)) - roots.begin());
	sort(all(vec), cmp);
	for(auto v : roots)
	{
		Size[v] = ted[v];
		///printf("v = %d Size = %lld\n", v, Size[v]);
	}
	for(int i = 1; i <= m + k; i ++)
	{
		V[i] = get(V[i]), U[i] = get(U[i]);
	}
	ROOT = get(1);
	for(int mask = 0; mask < 1 << k; mask ++)
	{
		solve(mask);
	}
	printf("%lld\n", tot);
	return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |   scanf("%d%d%d", &V[i], &U[i], &C[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:157:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   scanf("%d%d", &V[i], &U[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:160:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |  for(int i = 1; i <= n; i ++) { scanf("%d", &T[i]); }
      |                                 ~~~~~^~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 14 ms 21524 KB Output is correct
4 Correct 14 ms 21528 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 14 ms 21524 KB Output is correct
4 Correct 14 ms 21528 KB Output is correct
5 Correct 16 ms 21748 KB Output is correct
6 Correct 16 ms 21708 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 14 ms 21524 KB Output is correct
4 Correct 14 ms 21528 KB Output is correct
5 Correct 16 ms 21748 KB Output is correct
6 Correct 16 ms 21708 KB Output is correct
7 Correct 306 ms 37564 KB Output is correct
8 Correct 341 ms 37644 KB Output is correct
9 Correct 344 ms 37580 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 14 ms 21524 KB Output is correct
4 Correct 14 ms 21528 KB Output is correct
5 Correct 16 ms 21748 KB Output is correct
6 Correct 16 ms 21708 KB Output is correct
7 Correct 306 ms 37564 KB Output is correct
8 Correct 341 ms 37644 KB Output is correct
9 Correct 344 ms 37580 KB Output is correct
10 Execution timed out 2570 ms 37688 KB Time limit exceeded
11 Halted 0 ms 0 KB -