oj.uz

Submission #231806

# Submission time Handle Problem Language Result Execution time Memory
231806 2020-05-14T23:29:12 Z alishahali1382 Toll (APIO13_toll) C++14
100 / 100
 1997 ms 23140 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 300030, K=20;

ll n, m, k, u, v, x, y, t, a, b, ans;
int par[MAXN];
int E[MAXN][3];
int ind[MAXN];
ll P[MAXN];
bool good1[MAXN], good2[MAXN];
int parent[MAXN], parid[MAXN], h[MAXN];
ll sz[MAXN];
vector<pii> G[MAXN];

int getpar(int x){
	if (par[x]==x) return x;
	return par[x]=getpar(par[x]);
}

int join(int x, int y){
	x=getpar(x);
	y=getpar(y);
	if (x==y) return 0;
	par[x]=y;
	return 1;
}

void dfs(int node){
	sz[node]=P[node];
	for (pii p:G[node]) if (p.first!=parent[node]){
		parent[p.first]=node;
		parid[p.first]=p.second;
		h[p.first]=h[node]+1;
		dfs(p.first);
		sz[node]+=sz[p.first];
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>k;
	vector<pair<int, pii>> vec;
	while (m--){
		cin>>u>>v>>x;
		vec.pb({x, {u, v}});
	}
	sort(all(vec));
	m=0;
	for (auto p:vec){
		E[m][0]=p.second.first;
		E[m][1]=p.second.second;
		E[m++][2]=p.first;
	}
	
	for (int i=m; i<m+k; i++) cin>>E[i][0]>>E[i][1];
	for (int i=1; i<=n; i++) cin>>P[i];
	
	iota(par+1, par+n+1, 1);
	for (int i=0; i<m; i++) good1[i]=join(E[i][0], E[i][1]);
	
	iota(par+1, par+n+1, 1);
	for (int i=m; i<m+k; i++) join(E[i][0], E[i][1]);
	for (int i=0; i<m; i++) good2[i]=join(E[i][0], E[i][1]);
	
	
	vector<int> edge, V;
	iota(par+1, par+n+1, 1);
	for (int i=0; i<m; i++){
		if (good2[i]) join(E[i][0], E[i][1]);
		else if (good1[i]) edge.pb(i);
	}
	
	for (int i=0; i<m+k; i++) E[i][0]=getpar(E[i][0]), E[i][1]=getpar(E[i][1]);
	for (int i=1; i<=n; i++){
		if (par[i]!=i) P[getpar(i)]+=P[i], P[i]=0;
		else V.pb(i);
	}
	
	int root=getpar(1);
	
	for (int mask=0; mask<(1<<k); mask++){
		for (int v:V){
			par[v]=v;
			G[v].clear();
		}
		
		bool bad=0;
		for (int i=0; i<k && !bad; i++) if (mask&(1<<i)){
			int u=E[i+m][0], v=E[i+m][1];
			if (join(u, v)){
				G[u].pb({v, i+m});
				G[v].pb({u, i+m});
				E[i+m][2]=inf;
			}
			else bad=1;
		}
		if (bad) continue ;
		
		for (int e:edge){
			int u=E[e][0], v=E[e][1];
			if (join(u, v)){
				G[u].pb({v, e});
				G[v].pb({u, e});
			}
		}
		
		// should it be connected?!
		
		dfs(root);
		for (int e:edge){
			int u=E[e][0], v=E[e][1], w=E[e][2];
			while (u!=v){
				if (h[u]>h[v]) swap(u, v);
				if (parid[v]>=m) E[parid[v]][2]=min(E[parid[v]][2], w);
				v=parent[v];
			}
		}
		
		ll val=0;
		for (int v:V) if (parid[v]>=m) val+=sz[v]*E[parid[v]][2];
		
		ans=max(ans, val);
	}
	cout<<ans<<'\n';
	
	
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7808 KB Output is correct
6 Correct 11 ms 7808 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7808 KB Output is correct
6 Correct 11 ms 7808 KB Output is correct
7 Correct 231 ms 23000 KB Output is correct
8 Correct 235 ms 23136 KB Output is correct
9 Correct 245 ms 23000 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7808 KB Output is correct
6 Correct 11 ms 7808 KB Output is correct
7 Correct 231 ms 23000 KB Output is correct
8 Correct 235 ms 23136 KB Output is correct
9 Correct 245 ms 23000 KB Output is correct
10 Correct 1500 ms 23140 KB Output is correct
11 Correct 1963 ms 23128 KB Output is correct
12 Correct 1997 ms 23128 KB Output is correct