oj.uz

답안 #95990

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95990 2019-02-05T01:53:14 Z tmwilliamlin168 통행료 (APIO13_toll) C++14
100 / 100
 1840 ms 8684 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) {
		return x==p[x]?x:(p[x]=find(p[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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2808 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 182 ms 8576 KB Output is correct
8 Correct 245 ms 8544 KB Output is correct
9 Correct 195 ms 8568 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 182 ms 8576 KB Output is correct
8 Correct 245 ms 8544 KB Output is correct
9 Correct 195 ms 8568 KB Output is correct
10 Correct 1350 ms 8596 KB Output is correct
11 Correct 1810 ms 8680 KB Output is correct
12 Correct 1840 ms 8684 KB Output is correct