oj.uz

Submission #746494

# Submission time Handle Problem Language Result Execution time Memory
746494 2023-05-22T14:19:01 Z denniskim Toll (APIO13_toll) C++17
78 / 100
 2500 ms 23580 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

 
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
 
inline int readChar();
template<class T = int> inline T readInt();
template<class T> inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 1 << 18;
inline int getChar(){
    #ifndef LOCAL
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if(pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
    if(pos == len) return -1;
    return buf[pos++];
    #endif
}
inline int readChar(){
    #ifndef LOCAL
    int c = getChar();
    while(c <= 32) c = getChar();
    return c;
    #else
    char c; cin >> c; return c;
    #endif
}
template <class T>
inline T readInt(){
    #ifndef LOCAL
    int s = 1, c = readChar();
    T x = 0;
    if(c == '-') s = -1, c = getChar();
    while('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
    #else
    T x; cin >> x; return x;
    #endif
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x){
    if(write_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end){
    if(x < 0) writeChar('-'), x = -x;
    char s[24]; int n = 0;
    while(x || !n) s[n++] = '0' + x % 10, x /= 10;
    while(n--) writeChar(s[n]);
    if(end) writeChar(end);
}
inline void writeWord(const char *s){
    while(*s) writeChar(*s++);
}
struct Flusher{
    ~Flusher(){ if(write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0; }
}flusher;
 
struct edge
{
	ll u, v, cost;
	
	bool operator < (const edge &xx) const
	{
		return cost < xx.cost;
	}
};
 
ll n, m, K;
ll all, bll, cll;
vector<edge> edg;
vector< pair<pll, ll> > mst[3];
set< pair<pll, ll> > st;
pll ne[100010];
ll a[100010];
ll p[100010], ra[100010];
vector<ll> V;
vector< pair<pll, ll> > vec[30];
ll sum[100010];
ll siz;
ll grp[100010];
ll chk[30], last[30], len[30];
ll dp[30];
ll ans;
ll dep[30];
ll cc;
 
ll ffind(ll here)
{
	if(here == p[here])
		return here;
	
	return p[here] = ffind(p[here]);
}
 
void uunion(ll X, ll Y)
{
	X = ffind(X);
	Y = ffind(Y);
	
	if(X == Y)
		return;
	
	if(ra[X] < ra[Y])
		p[X] = Y;
	else if(ra[X] > ra[Y])
		p[Y] = X;
	
	else
	{
		p[X] = Y;
		ra[Y]++;
	}
}
 
void MST(ll num)
{
	for(ll i = 1 ; i <= n ; i++)
		p[i] = i, ra[i] = 0;
	
	sort(edg.begin(), edg.end());
	
	for(auto &i : edg)
	{
		if(ffind(i.u) == ffind(i.v))
			continue;
		
		uunion(i.u, i.v);
		mst[num].push_back({{min(i.u, i.v), max(i.u, i.v)}, i.cost});
	}
}
 
ll bi;
 
void dfs(ll here, ll pa)
{
	last[here] = pa;
	
	for(auto &i : vec[here])
	{
		if(i.fi.fi == pa)
			continue;
		
		if(i.se == 0)
			len[i.fi.fi] = i.fi.se;
		else
			len[i.fi.fi] = -INF;
		
		dfs(i.fi.fi, here);
	}
}
 
void add_edge(ll I)
{
	ll uu = ne[I].fi;
	ll vv = ne[I].se;
	
	bi = -INF;
	
	len[uu] = -INF;
	dfs(uu, 0);
	
	cc++;
	
	for(ll i = vv ; i != 0 ; i = last[i])
	{
		chk[i] = cc;
		bi = max(bi, len[i]);
	}
	
	if(bi == -INF)
		return;
	
	vector< pair<pll, ll> > help[30];
	
	for(ll i = 1 ; i <= siz ; i++)
	{
		for(auto &j : vec[i])
		{
			if(j.se == 1 && j.fi.se > bi && chk[i] == cc && chk[j.fi.fi] == cc)
				help[i].push_back({{j.fi.fi, bi}, j.se});
			else if(j.se == 0 && j.fi.se == bi)
				continue;
			else
				help[i].push_back(j);
		}
	}
	
	help[uu].push_back({{vv, bi}, 1});
	help[vv].push_back({{uu, bi}, 1});
	
	for(ll i = 1 ; i <= siz ; i++)
		vec[i] = help[i];
}
 
ll gap;
 
void dfs2(ll here, ll pa)
{
	dp[here] = sum[here];
	dep[here] = dep[pa] + 1;
	
	for(auto &i : vec[here])
	{
		if(i.fi.fi == pa)
			continue;
		
		dfs2(i.fi.fi, here);
		dp[here] += dp[i.fi.fi];
		
		if(i.se == 1)
			gap += dp[i.fi.fi] * i.fi.se;
	}
}
 
void f(ll here)
{
	if(here > K)
	{
		gap = 0;
		
		dfs2(grp[1], 0);
		
		ans = max(ans, gap);
		return;
	}
	
	f(here + 1);
	
	vector< pair<pll, ll> > tmp[30];
	
	for(ll i = 1 ; i <= siz ; i++)
		tmp[i] = vec[i];
	
	add_edge(here);
	f(here + 1);
	
	for(ll i = 1 ; i <= siz ; i++)
		vec[i] = tmp[i];
}
 
int main(void)
{
	fastio
	
	//cin >> n >> m >> K;
	n = readInt();
	m = readInt();
	K = readInt();
	
	for(ll i = 1 ; i <= m ; i++)
	{
		//cin >> all >> bll >> cll;
		
		all = readInt();
		bll = readInt();
		cll = readInt();
		edg.push_back({all, bll, cll});
	}
	
	for(ll i = 1 ; i <= K ; i++)
	{
		ne[i].fi = readInt();
		ne[i].se = readInt();
		//cin >> ne[i].fi >> ne[i].se;
	}
	
	for(ll i = 1 ; i <= n ; i++)
	{
		a[i] = readInt();
		//cin >> a[i];
	}
	
	MST(0);
	
	for(ll i = 1 ; i <= K ; i++)
		edg.push_back({ne[i].fi, ne[i].se, 0});
	
	MST(1);
	
	for(auto &i : mst[1])
		st.insert(i);
	
	for(ll i = 1 ; i <= n ; i++)
		p[i] = i, ra[i] = 0;
	
	for(auto &i : mst[0])
	{
		if(st.find(i) == st.end())
			mst[2].push_back(i);
		else
			uunion(i.fi.fi, i.fi.se);
	}
	
	for(ll i = 1 ; i <= n ; i++)
		V.push_back(ffind(i));
	
	compress(V);
	siz = (ll)V.size();
	
	for(ll i = 1 ; i <= n ; i++)
	{
		ll w = ffind(i);
		
		w = lower_bound(V.begin(), V.end(), w) - V.begin() + 1;
		grp[i] = w;
		sum[w] += a[i];
	}
	
	for(auto &i : mst[2])
	{
		ll v1 = ffind(i.fi.fi);
		ll v2 = ffind(i.fi.se);
		
		v1 = lower_bound(V.begin(), V.end(), v1) - V.begin() + 1;
		v2 = lower_bound(V.begin(), V.end(), v2) - V.begin() + 1;
		
		vec[v1].push_back({{v2, i.se}, 0});
		vec[v2].push_back({{v1, i.se}, 0});
	}
	
	for(ll i = 1 ; i <= K ; i++)
	{
		ne[i].fi = lower_bound(V.begin(), V.end(), ffind(ne[i].fi)) - V.begin() + 1;
		ne[i].se = lower_bound(V.begin(), V.end(), ffind(ne[i].se)) - V.begin() + 1;
	}
	
	f(1);
	
	writeInt(ans);
	Flusher();
	return 0;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 4 ms 660 KB Output is correct
6 Correct 3 ms 660 KB Output is correct
7 Correct 288 ms 23472 KB Output is correct
8 Correct 289 ms 23524 KB Output is correct
9 Correct 324 ms 23488 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 4 ms 660 KB Output is correct
6 Correct 3 ms 660 KB Output is correct
7 Correct 288 ms 23472 KB Output is correct
8 Correct 289 ms 23524 KB Output is correct
9 Correct 324 ms 23488 KB Output is correct
10 Execution timed out 2578 ms 23580 KB Time limit exceeded
11 Halted 0 ms 0 KB -