oj.uz

Submission #561058

# Submission time Handle Problem Language Result Execution time Memory
561058 2022-05-12T08:31:16 Z Koosha_mv Toll (APIO13_toll) C++14
100 / 100
 1597 ms 22596 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int K=22,N=5e5+99,inf=1e9;

int n,m,k,rt,ans,a[N],val[N],s[N],t[N],w[N],col[N],par[N],Par[N];
vector<int> vtx;

struct G{
	vector<pair<int,int>> g[K];
	vector<int> path;
	int Max,Ans;
	void addedge(int u,int v,int w){
		g[u].pb({v,+w});
		g[v].pb({u,+w});
	}
	void dfs(int u,int p,int x,int mx){
		par[u]=p;
		for(auto [v,w] : g[u]){
			if(v==p) continue ;
			dfs(v,u,x,max(mx,w));
		}
		if(mx!=0 && u==x){
			for(int now=u;;now=par[now]){
				path.pb(now);
				if(now==par[now]) break;
			}
			Max=mx;
		}
	}
	void Add(int u,int v){
		path.clear();
		dfs(u,u,v,0);
		if(path.size()==0) return ;
		f(i,0,path.size()-1){
			f_(j,g[path[i]].size()-1,0){
				int v=g[path[i]][j].F,w=g[path[i]][j].S;
				if(w<0 && v==path[i+1]) maxm(g[path[i]][j].S,-Max);
				if(w==Max) g[path[i]].erase(g[path[i]].begin()+j);
			}
		}
		f(i,1,path.size()){
			f_(j,g[path[i]].size()-1,0){
				int v=g[path[i]][j].F,w=g[path[i]][j].S;
				if(w<0 && v==path[i-1]) maxm(g[path[i]][j].S,-Max);
				if(w==Max) g[path[i]].erase(g[path[i]].begin()+j);
			}
		}
		g[u].pb({v,-Max});
		g[v].pb({u,-Max});
	}
	int dfs1(int u,int p){
		int sz=val[u];
		for(auto [v,w] : g[u]){
			if(v==p) continue ;
			int t=dfs1(v,u);
			sz+=t;
			if(w<0){
				Ans-=w*t;
			}
		}
		return sz;
	}
	int solve(){
		Ans=0;
		dfs1(rt,rt);
		return Ans;
	}
} graph[K];

void reset(){
	fill(Par,Par+N,-1);
}
bool cmp(int u,int v){
	return w[u]<w[v];
}
int getpar(int u){
	if(Par[u]<0) return u;
	return Par[u]=getpar(Par[u]);
}
void merge(int u,int v){
	u=getpar(u),v=getpar(v);
	if(u==v) return ;
	if(Par[u]>Par[v]) swap(u,v);
	Par[u]+=Par[v];
	Par[v]=u;
}
void solve(int x,int mask){
	maxm(ans,graph[x].solve());
	if(x==k) return ;
	graph[x+1]=graph[x];
	solve(x+1,mask);
	graph[x+1].Add(s[x],t[x]);
	solve(x+1,mask^(1<<x));
}
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	reset();
	cin>>n>>m>>k;
	f(i,k,k+m) cin>>s[i]>>t[i]>>w[i];
	f(i,0,k) cin>>s[i]>>t[i];
	f(i,1,n+1) cin>>a[i];
	vector<int> vec(k+m),Edge;
	iota(all(vec),0);
	sort(all(vec),cmp);
	for(auto id : vec){
		int u=s[id],v=t[id];
		if(getpar(u)!=getpar(v)){
			Edge.pb(id);
			merge(u,v);
		}
	}
	reset();
	while(Edge.back()>=k){
		merge(s[Edge.back()],t[Edge.back()]);
		Edge.pop_back();
	}
	Edge.clear();
	int cnt=0;
	f(i,1,n+1) if(getpar(i)==i) col[i]=cnt++;
	f(i,1,n+1) col[i]=col[getpar(i)],val[col[i]]+=a[i];
	rt=col[1];
	vec.resize(m); m=k;
	iota(all(vec),k);
	sort(all(vec),cmp);
	for(auto id : vec){
		if(getpar(s[id])!=getpar(t[id])){
			merge(s[id],t[id]);
			Edge.pb(id);
		}
	}
	sort(all(Edge));
	f(i,0,Edge.size()){
		//eror(Edge[i]);
		s[k+i]=s[Edge[i]],t[k+i]=t[Edge[i]],w[k+i]=w[Edge[i]];
		m++;
	}
	f(i,0,m){
		s[i]=col[s[i]],t[i]=col[t[i]];
		//cout<<s[i]<<" "<<t[i]<<" "<<w[i]<<endl;
	}
	f(i,k,m) graph[0].addedge(s[i],t[i],w[i]);
	solve(0,0);
	cout<<ans;
}
/*
5 4 2
1 2 10
2 3 20
3 4 6
4 5 3
1 3
3 5
100 100 100 100 100
*/

Compilation message

toll.cpp: In member function 'void G::dfs(long long int, long long int, long long int, long long int)':
toll.cpp:38:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |   for(auto [v,w] : g[u]){
      |            ^
toll.cpp: In member function 'void G::Add(long long int, long long int)':
toll.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   54 |   f(i,0,path.size()-1){
      |     ~~~~~~~~~~~~~~~~~          
toll.cpp:54:3: note: in expansion of macro 'f'
   54 |   f(i,0,path.size()-1){
      |   ^
toll.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   61 |   f(i,1,path.size()){
      |     ~~~~~~~~~~~~~~~            
toll.cpp:61:3: note: in expansion of macro 'f'
   61 |   f(i,1,path.size()){
      |   ^
toll.cpp: In member function 'long long int G::dfs1(long long int, long long int)':
toll.cpp:73:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |   for(auto [v,w] : g[u]){
      |            ^
toll.cpp: In function 'int32_t main()':
toll.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
  152 |  f(i,0,Edge.size()){
      |    ~~~~~~~~~~~~~~~             
toll.cpp:152:2: note: in expansion of macro 'f'
  152 |  f(i,0,Edge.size()){
      |  ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 5 ms 4436 KB Output is correct
6 Correct 17 ms 4436 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 5 ms 4436 KB Output is correct
6 Correct 17 ms 4436 KB Output is correct
7 Correct 273 ms 22552 KB Output is correct
8 Correct 299 ms 22556 KB Output is correct
9 Correct 296 ms 22568 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 5 ms 4436 KB Output is correct
6 Correct 17 ms 4436 KB Output is correct
7 Correct 273 ms 22552 KB Output is correct
8 Correct 299 ms 22556 KB Output is correct
9 Correct 296 ms 22568 KB Output is correct
10 Correct 996 ms 22548 KB Output is correct
11 Correct 1597 ms 22596 KB Output is correct
12 Correct 1561 ms 22560 KB Output is correct