oj.uz

Submission #794339

# Submission time Handle Problem Language Result Execution time Memory
794339 2023-07-26T13:00:01 Z 곰(#10095) Travelling Trader (CCO23_day2problem2) C++17
11 / 25
 223 ms 55700 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using pll=array<ll,2>;
const ll inf=1e18;
const int N=2e5+5;
int n,k;
ll a[N],s[N],dp[N][4];
vector<int> g[N],c[N],cc[N],ans;
void dfs1(int u,int p){
	dp[u][0]=a[u];
	for(int v: g[u]) if(p!=v){
		c[u].emplace_back(v);
		dfs1(v,u);
		dp[u][0]=max(dp[u][0],dp[v][0]+a[u]);
	}
}
void track1(int u){
	ans.emplace_back(u);
	for(int v: c[u]) if(dp[u][0]==dp[v][0]+a[u]){
		track1(v);
		return;
	}
}
void dfs2(int u,int p){
	s[u]=a[u];
	for(int v: g[u]) if(p!=v){
		cc[u].emplace_back(v);
		dfs2(v,u);
		s[u]+=a[v];
	}
	for(int t=0;t<4;t++){
		sort(cc[u].begin(),cc[u].end(),[&](int i,int j){
			return dp[i][t]-a[i]>dp[j][t]-a[j];
		});
		for(int i=0;i<min((int)cc[u].size(),10);i++) c[u].emplace_back(cc[u][i]);
	}
	{
		sort(cc[u].begin(),cc[u].end(),[&](int i,int j){
			return dp[i][3]>dp[j][3];
		});
		for(int i=0;i<min((int)cc[u].size(),10);i++) c[u].emplace_back(cc[u][i]);
	}
	sort(c[u].begin(),c[u].end());
	c[u].resize(unique(c[u].begin(),c[u].end())-c[u].begin());
	dp[u][0]=a[u];
	dp[u][1]=a[u];
	dp[u][2]=a[u];
	dp[u][3]=a[u];
	for(int v: c[u]){
		dp[u][0]=max(dp[u][0],dp[v][0]+s[u]-a[v]);
		dp[u][0]=max(dp[u][0],dp[v][3]+a[u]);
		for(int w: c[u]) if(v!=w){
			dp[u][0]=max(dp[u][0],dp[v][1]+dp[w][0]+s[u]-a[v]-a[w]);
		}
		dp[u][1]=max(dp[u][1],dp[v][2]+s[u]-a[v]);
		dp[u][2]=max(dp[u][2],dp[v][1]+s[u]-a[v]);
		for(int w: c[u]) if(v!=w){
			dp[u][3]=max(dp[u][3],dp[v][2]+dp[w][3]+s[u]-a[v]-a[w]);
			for(int x: c[u]) if(v!=x&&w!=x){
				dp[u][3]=max(dp[u][3],dp[v][2]+dp[w][1]+dp[x][0]+s[u]-a[v]-a[w]-a[x]);
			}
		}
	}
	dp[u][3]=max(dp[u][3],dp[u][0]);
}
void track2(int u,int d){
	if(d==0){
		ans.emplace_back(u);
		for(int v: c[u]){
			if(dp[u][0]==dp[v][0]+s[u]-a[v]){
				for(int w: c[u]) if(v!=w) ans.emplace_back(w);
				track2(v,0);
				return;
			}
			if(dp[u][0]==dp[v][3]+a[u]){
				track2(v,3);
				return;
			}
		}
		for(int v: c[u]) for(int w: c[u]) if(v!=w&&dp[u][0]==dp[v][1]+dp[w][0]+s[u]-a[v]-a[w]){
			track2(v,1);
			for(int x: c[u]) if(v!=x&&w!=x) ans.emplace_back(x);
			track2(w,0);
			return;
		}
	} else if(d==1){
		for(int v: c[u]) if(dp[u][1]==dp[v][2]+s[u]-a[v]){
			for(int w: c[u]) if(v!=w) ans.emplace_back(w);
			track2(v,2);
			ans.emplace_back(u);
			return;
		}
		ans.emplace_back(u);
	} else if(d==2){
		ans.emplace_back(u);
		for(int v: c[u]) if(dp[u][2]==dp[v][1]+s[u]-a[v]){
			track2(v,1);
			for(int w: c[u]) if(v!=w) ans.emplace_back(w);
			return;
		}
	} else{
		if(dp[u][3]==dp[u][0]){
			track2(u,0);
			return;
		}
		for(int v: c[u]){
			for(int w: c[u]) if(v!=w){
				if(dp[u][3]==dp[v][2]+dp[w][3]+s[u]-a[v]-a[w]){
					for(int x: c[u]) if(v!=x&&w!=x) ans.emplace_back(x);
					track2(v,2);
					ans.emplace_back(u);
					track2(w,3);
					return;
				}
				for(int x: c[u]) if(v!=x&&w!=x){
					if(dp[u][3]==dp[v][2]+dp[w][1]+dp[x][0]+s[u]-a[v]-a[w]-a[x]){
						debug(v,w,x);
						track2(v,2);
						ans.emplace_back(u);
						track2(w,1);
						for(int y: c[u]) if(v!=y&&w!=y&&x!=y) ans.emplace_back(y);
						track2(x,0);
						return;
					}
				}
			}
		}
	}
}
void dfs3(int u,int p){
	ans.emplace_back(u);
	for(int v: g[u]) if(p!=v){
		for(int w: g[v]) if(u!=w){
			dfs3(w,v);
		}
		ans.emplace_back(v);
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k;
	for(int u,v,i=1;i<n;i++){
		cin>>u>>v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	for(int i=1;i<=n;i++) cin>>a[i];
	if(k==1){
		dfs1(1,0);
		cout<<dp[1][0]<<"\n";
		track1(1);
	} else if(k==2){
		dfs2(1,0);
		cout<<dp[1][0]<<"\n";
		track2(1,0);
		ll S=0;
		for(int u: ans) S+=a[u];
		assert(dp[1][0]==S);
	} else if(k==3){
		dfs3(1,0);
		cout<<accumulate(a+1,a+n+1,0ll)<<"\n";
	}
	cout<<ans.size()<<"\n";
	for(int u: ans) cout<<u<<" ";
	return 0;
}

Compilation message

Main.cpp: In function 'void track2(int, int)':
Main.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
Main.cpp:126:7: note: in expansion of macro 'debug'
  126 |       debug(v,w,x);
      |       ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 127 ms 31948 KB Output is correct
4 Correct 150 ms 31848 KB Output is correct
5 Correct 137 ms 32472 KB Output is correct
6 Correct 119 ms 30956 KB Output is correct
7 Correct 77 ms 30760 KB Output is correct
8 Correct 107 ms 32324 KB Output is correct
9 Correct 223 ms 55700 KB Output is correct
10 Correct 182 ms 42092 KB Output is correct
11 Correct 75 ms 31544 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14548 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14456 KB Output is correct
6 Correct 10 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Runtime error 23 ms 29140 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14548 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14456 KB Output is correct
6 Correct 10 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Runtime error 23 ms 29140 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14548 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14456 KB Output is correct
6 Correct 10 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Runtime error 23 ms 29140 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14556 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 9 ms 14556 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 10 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 8 ms 14428 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 11 ms 14420 KB Output is correct
11 Correct 11 ms 14420 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 10 ms 14420 KB Output is correct
15 Correct 9 ms 14420 KB Output is correct
16 Correct 10 ms 14420 KB Output is correct
17 Correct 11 ms 14548 KB Output is correct
18 Correct 11 ms 14548 KB Output is correct
19 Correct 9 ms 14420 KB Output is correct
20 Correct 9 ms 14464 KB Output is correct
21 Correct 8 ms 14548 KB Output is correct
22 Correct 9 ms 14564 KB Output is correct
23 Correct 9 ms 14540 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14556 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 9 ms 14556 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 10 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 8 ms 14428 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 11 ms 14420 KB Output is correct
11 Correct 11 ms 14420 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 10 ms 14420 KB Output is correct
15 Correct 9 ms 14420 KB Output is correct
16 Correct 10 ms 14420 KB Output is correct
17 Correct 11 ms 14548 KB Output is correct
18 Correct 11 ms 14548 KB Output is correct
19 Correct 9 ms 14420 KB Output is correct
20 Correct 9 ms 14464 KB Output is correct
21 Correct 8 ms 14548 KB Output is correct
22 Correct 9 ms 14564 KB Output is correct
23 Correct 9 ms 14540 KB Output is correct
24 Correct 104 ms 24632 KB Output is correct
25 Correct 120 ms 24668 KB Output is correct
26 Correct 119 ms 24632 KB Output is correct
27 Correct 107 ms 24564 KB Output is correct
28 Correct 104 ms 24568 KB Output is correct
29 Correct 118 ms 24488 KB Output is correct
30 Correct 98 ms 25184 KB Output is correct
31 Correct 119 ms 24524 KB Output is correct
32 Correct 115 ms 25228 KB Output is correct
33 Correct 110 ms 24544 KB Output is correct
34 Correct 101 ms 25380 KB Output is correct
35 Correct 78 ms 25148 KB Output is correct
36 Correct 108 ms 24756 KB Output is correct
37 Correct 108 ms 24568 KB Output is correct
38 Correct 128 ms 25356 KB Output is correct
39 Correct 144 ms 35376 KB Output is correct
40 Correct 106 ms 29932 KB Output is correct
41 Correct 122 ms 28088 KB Output is correct
42 Correct 203 ms 27156 KB Output is correct
43 Correct 113 ms 25756 KB Output is correct
44 Correct 154 ms 25532 KB Output is correct
45 Correct 81 ms 24404 KB Output is correct
46 Correct 76 ms 24360 KB Output is correct