oj.uz

Submission #561060

# Submission time Handle Problem Language Result Execution time Memory
561060 2022-05-12T08:32:21 Z Koosha_mv Toll (APIO13_toll) C++14
100 / 100
 1470 ms 16520 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){
	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

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 2 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 2 ms 4180 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4256 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 2 ms 4180 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4256 KB Output is correct
5 Correct 5 ms 4500 KB Output is correct
6 Correct 5 ms 4564 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 2 ms 4180 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4256 KB Output is correct
5 Correct 5 ms 4500 KB Output is correct
6 Correct 5 ms 4564 KB Output is correct
7 Correct 214 ms 16492 KB Output is correct
8 Correct 268 ms 16520 KB Output is correct
9 Correct 229 ms 16508 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 2 ms 4180 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4256 KB Output is correct
5 Correct 5 ms 4500 KB Output is correct
6 Correct 5 ms 4564 KB Output is correct
7 Correct 214 ms 16492 KB Output is correct
8 Correct 268 ms 16520 KB Output is correct
9 Correct 229 ms 16508 KB Output is correct
10 Correct 935 ms 16504 KB Output is correct
11 Correct 1470 ms 16500 KB Output is correct
12 Correct 1445 ms 16508 KB Output is correct