oj.uz

답안 #207992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207992 2020-03-09T16:05:12 Z dennisstar 통행료 (APIO13_toll) C++17
100 / 100
 1665 ms 18796 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MX = 100005;

struct UF {
	int pr[MX];
	void init(int X) { fill(pr, pr+X+1, 0); }
	int gp(int x) { return pr[x]?(pr[x]=gp(pr[x])):x; }
	bool Un(int x, int y) {
		x=gp(x), y=gp(y);
		if (x!=y) pr[y]=x;
		return x!=y;
	}
}U;

int N, M, K, T, in[MX], chk[50], D[50], P[50], Mn[50];
ll C[MX], sz[50], Pp[50], A;
vector<pair<int, pii> > Ei, Eu, Ep, Eq;
vector<pii> New, adj[50]; vector<int> im[MX];

void dfs1(int n, int m) {
	in[n]=m; sz[m]+=C[n];
	for (auto &i:im[n]) if (!in[i]) dfs1(i, m);
}

void dfs2(int n, int p) {
	Pp[n]=sz[n], D[n]=D[p]+1, P[n]=p;
	for (auto &i:adj[n]) if (i.fi!=p)
		chk[i.fi]=i.se, dfs2(i.fi, n), Pp[n]+=Pp[i.fi];
}

void cpr() {
	U.init(N);
	for (auto &i:New) U.Un(i.fi, i.se);
	for (auto &i:Eu) {
		if (U.Un(i.se.fi, i.se.se)) im[i.se.fi].eb(i.se.se), im[i.se.se].eb(i.se.fi);
		else Ep.eb(i);
	}
	for (int i=1; i<=N; i++) if (!in[i]) dfs1(i, ++T);
	for (auto &i:New) i.fi=in[i.fi], i.se=in[i.se];
	for (auto &i:Ep) i.se.fi=in[i.se.fi], i.se.se=in[i.se.se];
}

void sol(int B) {
	U.init(T);
	for (int i=1; i<=T; i++) adj[i].clear(), Mn[i]=3<<29;
	for (int i=0; i<K; i++) if ((1<<i)&B) {
		if (!U.Un(New[i].fi, New[i].se)) return ;
		adj[New[i].fi].eb(New[i].se, 1), adj[New[i].se].eb(New[i].fi, 1);
	}
	Eq.clear();
	for (auto &i:Ep) {
		if (U.Un(i.se.fi, i.se.se))
			adj[i.se.fi].eb(i.se.se, 0), adj[i.se.se].eb(i.se.fi, 0);
		else Eq.eb(i);
	}
	dfs2(1, 0);
	for (auto &i:Eq) {
		int f, s; f=i.se.fi, s=i.se.se;
		if (D[f]>D[s]) swap(f, s);
		while (D[f]<D[s]) Mn[s]=min(Mn[s], i.fi), s=P[s];
		while (f!=s) Mn[f]=min(Mn[f], i.fi), Mn[s]=min(Mn[s], i.fi), f=P[f], s=P[s];
	}
	ll E=0; for (int i=1; i<=T; i++) if (chk[i]) E+=Pp[i]*Mn[i];
	A=max(A, E);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>N>>M>>K; Ei.resize(M);
	for (auto &i:Ei) cin>>i.se.fi>>i.se.se>>i.fi; 
	sort(all(Ei));
	for (auto &i:Ei) if (U.Un(i.se.fi, i.se.se)) Eu.eb(i);
	New.resize(K); for (auto &i:New) cin>>i.fi>>i.se;
	for (int i=1; i<=N; i++) cin>>C[i]; cpr();
	for (int i=0; i<(1<<K); i++) sol(i);
	cout<<A<<'\n';
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:82:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i=1; i<=N; i++) cin>>C[i]; cpr();
  ^~~
toll.cpp:82:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i=1; i<=N; i++) cin>>C[i]; cpr();
                                      ^~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 7 ms 2680 KB Output is correct
5 Correct 9 ms 2808 KB Output is correct
6 Correct 9 ms 2808 KB Output is correct
7 Correct 247 ms 12240 KB Output is correct
8 Correct 251 ms 18560 KB Output is correct
9 Correct 236 ms 18540 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 7 ms 2680 KB Output is correct
5 Correct 9 ms 2808 KB Output is correct
6 Correct 9 ms 2808 KB Output is correct
7 Correct 247 ms 12240 KB Output is correct
8 Correct 251 ms 18560 KB Output is correct
9 Correct 236 ms 18540 KB Output is correct
10 Correct 1368 ms 18796 KB Output is correct
11 Correct 1665 ms 18644 KB Output is correct
12 Correct 1649 ms 18672 KB Output is correct