Submission #561060

#	Time	Username	Problem	Language	Result	Execution time	Memory
561060		Koosha_mv	Toll (APIO13_toll)	C++14	100 / 100	1470 ms	16520 KiB

toll

#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){
	maxm(ans,graph[x].solve());
	if(x==k) return ;
	graph[x+1]=graph[x];
	solve(x+1);
	graph[x+1].Add(s[x],t[x]);
	solve(x+1);
}
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()){
		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]];
	f(i,k,m) graph[0].addedge(s[i],t[i],w[i]);
	solve(0);
	cout<<ans;
}

Compilation message (stderr)

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 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22