oj.uz

Submission #207992

# Submission time Handle Problem Language Result Execution time Memory
207992 2020-03-09T16:05:12 Z dennisstar Toll (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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