oj.uz

Submission #95991

# Submission time Handle Problem Language Result Execution time Memory
95991 2019-02-05T01:59:31 Z tmwilliamlin168 Toll (APIO13_toll) C++14
100 / 100
 1758 ms 8716 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;
	n1 operator+(const n1 &o) const {
		return r^o.r?n1{max(r, o.r)}:n1{r+1};
	}
	bool operator<(const n1 &o) const {
		return r<o.r;
	}
};

struct n2 {
	int r, a;
	n2 operator+(const n2 &o) const {
		return r^o.r?n2{max(r, o.r), a}:n2{r+1 ,a};
	}
	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 2680 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 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2552 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 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 6 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 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 173 ms 8668 KB Output is correct
8 Correct 181 ms 8668 KB Output is correct
9 Correct 179 ms 8668 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 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 173 ms 8668 KB Output is correct
8 Correct 181 ms 8668 KB Output is correct
9 Correct 179 ms 8668 KB Output is correct
10 Correct 1267 ms 8716 KB Output is correct
11 Correct 1758 ms 8696 KB Output is correct
12 Correct 1747 ms 8704 KB Output is correct