oj.uz

Submission #95992

# Submission time Handle Problem Language Result Execution time Memory
95992 2019-02-05T02:01:28 Z tmwilliamlin168 Toll (APIO13_toll) C++14
100 / 100
 1728 ms 8728 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5, mxK=20, mxM=3e5;
int n, k, m, r[mxN], p[mxK+1], d[mxK+1], rs, w[mxK+1];
array<int, 3> e[mxM];
array<int, 2> a[mxK];
vector<int> adj[mxN], b;
ll s[mxK+1], ans;

struct n1 {
	int r;
	__attribute__((always_inline)) n1 operator+(const n1 &o) const {
		return r^o.r?n1{max(r, o.r)}:n1{r+1};
	}
	__attribute__((always_inline)) bool operator<(const n1 &o) const {
		return r<o.r;
	}
};

struct n2 {
	int r, a;
	__attribute__((always_inline)) n2 operator+(const n2 &o) const {
		return r^o.r?n2{max(r, o.r), a}:n2{r+1 ,a};
	}
	__attribute__((always_inline)) bool operator<(const n2 &o) const {
		return r<o.r;
	}
};

template<size_t S, class T>
struct dsu {
	int p[S];
	T a[S];
	int find(int x) {
		while(x!=p[x])
			x=p[x]=p[p[x]];
		return x;
	}
	bool join(int x, int y) {
		if((x=find(x))==(y=find(y)))
			return 0;
		if(a[x]<a[y])
			p[y]=x;
		else
			p[x]=y;
		a[x]=a[y]=a[x]+a[y];
		return 1;
	}
};
dsu<mxN, n1> d1, d2, d3;
dsu<mxK+1, n1> d4;
dsu<mxK+1, n2> d5;

void dfs1(int u, int pu=-1) {
	p[u]=pu;
	d[u]=pu^-1?d[pu]+1:0;
	for(int v : adj[u])
		if(v!=pu)
			dfs1(v, u);
}

ll dfs2(int u, ll d=0) {
	ll r=d*s[u];
	for(int v : adj[u])
		if(v!=p[u])
			r+=dfs2(v, d+w[v]);
	return r;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;
	for(int i=0; i<m; ++i)
		cin >> e[i][1] >> e[i][2] >> e[i][0], --e[i][1], --e[i][2];
	sort(e, e+m);
	iota(d1.p, d1.p+n, 0);
	for(int i=0; i<k; ++i) {
		cin >> a[i][0] >> a[i][1], --a[i][0], --a[i][1];
		d1.join(a[i][0], a[i][1]);
	}
	iota(d2.p, d2.p+n, 0);
	iota(d3.p, d3.p+n, 0);
	for(int i=0; i<m; ++i) {
		if(!d2.join(e[i][1], e[i][2]))
			continue;
		if(d1.join(e[i][1], e[i][2]))
			d3.join(e[i][1], e[i][2]);
		else
			b.push_back(i);
	}
	for(int i=0; i<n; ++i)
		if(d3.find(i)==i)
			r[i]=rs++;
	for(int i=0, si; i<n; ++i) {
		cin >> si;
		s[r[d3.find(i)]]+=si;
	}
	for(int bi : b) {
		e[bi][1]=r[d3.find(e[bi][1])];
		e[bi][2]=r[d3.find(e[bi][2])];
	}
	for(int i=0; i<k; ++i) {
		a[i][0]=r[d3.find(a[i][0])];
		a[i][1]=r[d3.find(a[i][1])];
	}
	for(int i=0; i<1<<k; ++i) {
		for(int j=0; j<rs; ++j) {
			adj[j].clear();
			d5.a[j]={0, j};
		}
		iota(d4.p, d4.p+rs, 0);
		memset(d4.a, 0, sizeof(d4.a));
		iota(d5.p, d5.p+rs, 0);
		for(int j=0; j<k; ++j) {
			if(i>>j&1&&d4.join(a[j][0], a[j][1])) {
				adj[a[j][0]].push_back(a[j][1]);
				adj[a[j][1]].push_back(a[j][0]);
			}
		}
		deque<array<int, 3>> c;
		for(int bi : b) {
			if(d4.join(e[bi][1], e[bi][2])) {
				adj[e[bi][1]].push_back(e[bi][2]);
				adj[e[bi][2]].push_back(e[bi][1]);
				c.push_front({0, e[bi][1], e[bi][2]});
			} else
				c.push_back(e[bi]);
		}
		dfs1(r[d3.find(0)]);
		for(array<int, 3> ci : c) {
			int u=d5.a[d5.find(ci[1])].a, v=d5.a[d5.find(ci[2])].a;
			while(u^v) {
				if(d[u]<d[v])
					swap(u, v);
				w[u]=ci[0];
				d5.join(p[u], u);
				u=d5.a[d5.find(u)].a;
			}
		}
		ans=max(dfs2(r[d3.find(0)]), ans);
	}
	cout << ans;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 173 ms 8664 KB Output is correct
8 Correct 183 ms 8728 KB Output is correct
9 Correct 183 ms 8560 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 173 ms 8664 KB Output is correct
8 Correct 183 ms 8728 KB Output is correct
9 Correct 183 ms 8560 KB Output is correct
10 Correct 1359 ms 8696 KB Output is correct
11 Correct 1728 ms 8696 KB Output is correct
12 Correct 1723 ms 8696 KB Output is correct