Submission #355162

#	Time	Username	Problem	Language	Result	Execution time	Memory
355162		songc	Toll (APIO13_toll)	C++14	78 / 100	2558 ms	19948 KiB

toll

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
#define MOD 1'000'000'007 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, K, bi;
int P[101010], U[30], V[30];
LL A[101010], ans, sum;
vector<pii> adj[101010];
bool chk[101010];

int rt(int u){
	if (u == P[u]) return u;
	return P[u] = rt(P[u]);
}

struct Edge{
	LL u, v, w;
} edg[303030];
vector<Edge> E[101010];

int dfs1(int u, int p){
	int cnt=0;
	for (pii v : adj[u]){
		if (v.fi == p) continue;
		int p = dfs1(v.fi, u);
		if (!p) A[u] += A[v.fi];
		cnt += p;
	}
	if (cnt >= 2) chk[u] = true;
	if (cnt || chk[u]) return 1;
	return 0;
}

void dfs2(int u, int p, int pp, int mx, LL ps, LL s){
	if (chk[u]){
		if (u>1){
			E[pp].pb((Edge){u, ps, mx});
			E[u].pb((Edge){pp, s-ps, mx});
		}
		pp=u, mx=0, ps=0, s=-A[u];
	}
	for (pii v : adj[u]){
		if (v.fi == p) continue;
		if (mx < v.se) dfs2(v.fi, u, pp, v.se, s+A[u], s+A[u]);
		else dfs2(v.fi, u, pp, mx, ps, s+A[u]);
	}
}

pii path(int u, int p, int t, int mx, pii r){
	if (u == t) return r;
	for (int i=0; i<E[u].size(); i++){
		if (E[u][i].u == p) continue;
		pii ret = pii(0,0);
		if (E[u][i].w > mx && E[u][i].v != -1) ret = path(E[u][i].u, u, t, E[u][i].w, pii(u, E[u][i].u));
		else ret = path(E[u][i].u, u, t, mx, r);
		if (ret != pii(0,0)) return ret;
	}
	return pii(0, 0);
}

bool upd(int u, int p, int t, int x, vector<Edge> &rb){
	if (u == t) return true;
	for (int i=0; i<E[u].size(); i++){
		if (E[u][i].u == p) continue;
		if (upd(E[u][i].u, u, t, x, rb)){
			if (E[u][i].v < 0 && E[u][i].w > x){
				rb.pb((Edge){u, E[u][i].u, E[u][i].w});
				E[u][i].w = x;
			}
			return true;
		}
	}
	return false;
}

LL calc(int u, int p){
	LL w = A[u];
	for (int i=0; i<E[u].size(); i++){
		if (E[u][i].u == p){
			if (E[u][i].v != -1) w += E[u][i].v;
			continue;
		}
		LL r = calc(E[u][i].u, u);
		if (E[u][i].v < 0) sum += E[u][i].w * r;
		else r += E[u][i].v;
		w += r;
	}
	return w;
}

Edge del(int u, int v){
	Edge ret;
	for (int i=0; i<E[u].size(); i++) if (E[u][i].u == v){
		ret = E[u][i];
		swap(E[u][i], E[u].back());
		E[u].pop_back();
	}
	return ret;
}

void bt(int k){
	if (k > K){
		sum = 0, calc(1, 0);
		ans = max(ans, sum);
		return;
	}
	bi <<= 1;
	bt(k+1);
	bi >>= 1;

	int u, v;
	tie(u, v) = path(U[k], 0, V[k], 0, pii(0,0));
	if (!u) return;
	Edge eu = del(u, v), ev = del(v, u);
	A[u] += eu.v, A[v] += ev.v;
	E[U[k]].pb((Edge){V[k], -1, eu.w});
	E[V[k]].pb((Edge){U[k], -1, eu.w});
	vector<Edge> rb;
	upd(u, 0, v, eu.w, rb);
	upd(v, 0, u, eu.w, rb);
	
	bi <<= 1;
	bi += 1;
	bt(k+1);
	bi >>= 1;

	for (Edge it : rb){
		del(it.u, it.v), del(it.v, it.u);
		E[it.u].pb((Edge){it.v, -1, it.w});
		E[it.v].pb((Edge){it.u, -1, it.w});
	}
	rb.clear();
	del(U[k], V[k]), del(V[k], U[k]);
	E[u].pb(eu), E[v].pb(ev);
	A[u] -= eu.v, A[v] -= ev.v;
}

int main(){
	scanf("%d %d %d", &N, &M, &K);
	for (int i=1; i<=M; i++) scanf("%lld %lld %lld", &edg[i].u, &edg[i].v, &edg[i].w);
	for (int i=1; i<=N; i++) P[i] = i;
	sort(edg+1, edg+M+1, [&](Edge a, Edge b){return a.w < b.w;});
	for (int i=1; i<=M; i++){
		if (rt(edg[i].u) == rt(edg[i].v)) continue;
		P[rt(edg[i].u)] = rt(edg[i].v);
		adj[edg[i].u].pb(pii(edg[i].v, edg[i].w));
		adj[edg[i].v].pb(pii(edg[i].u, edg[i].w));
	}
	chk[1] = true;
	for (int i=1; i<=K; i++){
		scanf("%d %d", &U[i], &V[i]);
		chk[U[i]] = chk[V[i]] = true;
	}
	for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
	dfs1(1, 0);
	dfs2(1, 0, 0, 0, 0, 0);
	bt(1);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'pii path(int, int, int, int, pii)':
toll.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i=0; i<E[u].size(); i++){
      |                ~^~~~~~~~~~~~
toll.cpp: In function 'bool upd(int, int, int, int, std::vector<Edge>&)':
toll.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i=0; i<E[u].size(); i++){
      |                ~^~~~~~~~~~~~
toll.cpp: In function 'LL calc(int, int)':
toll.cpp:88:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i=0; i<E[u].size(); i++){
      |                ~^~~~~~~~~~~~
toll.cpp: In function 'Edge del(int, int)':
toll.cpp:103:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i=0; i<E[u].size(); i++) if (E[u][i].u == v){
      |                ~^~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |  scanf("%d %d %d", &N, &M, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:150:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |  for (int i=1; i<=M; i++) scanf("%lld %lld %lld", &edg[i].u, &edg[i].v, &edg[i].w);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:161:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  161 |   scanf("%d %d", &U[i], &V[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:164:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  164 |  for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 0 / 22