Educational Codeforces Round 114 (Rated for Div. 2) D

D. The Strongest Build

The question ：
Here you are. $n$ A place （$n<=10$）, Each location has $ci$ Number of alternatives ($ci<=200000$), Then there is $m$ A combination of ($m<=200000$), Find other than these combinations And the biggest combination , Output Max sum .

Ideas One ：
according to $m$ A limit , Build a dictionary tree , Then traverse the dictionary tree , At the current point , Ensure that the number from the current point to the root , The position below is greedy , The maximum value after traversing the dictionary tree is the answer . Use the segment tree to maintain the greedy method of the following position .

Code ：
The code is more complex , Looking for mistakes all day , And the dictionary tree is badly written … crying , however AC It proves that it can be achieved in the competition .

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,m;
int num[12];
struct node{
    
	int id,w;
}z[11][200004];
bool cmp(node a,node b){
    
	return a.w>b.w;
}
int tot=0;
int pre[12];
int id[11][200004];
struct {
    
	map<int,int>mp;
	vector<int>v;
}trie[2000005];
int tr[11][800006];
int ans=0;
stack<int>sta,ans1;
int ff=-1;
void build(int id,int p,int l,int r){
    
	tr[id][p]=0;
	if(l==r)return ;
	int mid=l+r>>1;
	build(id,2*p,l,mid);
	build(id,2*p+1,mid+1,r);
}
void update(int id,int p,int l,int r,int x,int y,int w){
    
	if(l==r){
    
		tr[id][p]+=w;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)update(id,2*p,l,mid,x,y,w);
	else update(id,2*p+1,mid+1,r,x,y,w);
	tr[id][p]=tr[id][2*p]+tr[id][2*p+1];
}
int query(int id,int p,int l,int r){
    
	if(l==r){
    
		if(tr[id][p]==0)return l;
		else return -1;
	}
	int mid=l+r>>1;
	if(tr[id][2*p]!=mid-l+1)return query(id,2*p,l,mid);
	else return query(id,2*p+1,mid+1,r);
}
void dfs(int x,int y,int w,int id){
    
	if(x!=0)update(x,1,1,num[x],y,y,1);
	if(x!=0&&x!=n)sta.push(y);
	if(x==n)return;
	for(int i=0;i<trie[id].v.size();i++){
    
		int too=trie[id].v[i];
		int to=trie[id].mp[too];
		dfs(x+1,too,w+z[x][y].w,to);
	}
	int fla=query(x+1,1,1,num[x+1]);
	if(fla!=-1){
    
		if(w+z[x+1][fla].w+pre[x+2]+z[x][y].w>ans){
    
			ans=w+z[x+1][fla].w+pre[x+2]+z[x][y].w;
			ans1=sta;
			ff=fla;
		}
	}
	if(x!=0)sta.pop();
	for(int i=0;i<trie[id].v.size();i++){
    
		int too=trie[id].v[i];
		int to=trie[id].mp[too];
		update(x+1,1,1,num[x+1],too,too,-1);
	}
}
int main(){
    
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	z[0][0].w=0;
	for(int i=1;i<=n;i++){
    
		cin>>num[i];
		for(int j=1;j<=num[i];j++){
    
			cin>>z[i][j].w;
			z[i][j].id=j;
		}
		sort(z[i]+1,z[i]+1+num[i],cmp);
		for(int j=1;j<=num[i];j++){
    
			id[i][z[i][j].id]=j;
		}
	}
	pre[n+1]=0;
	for(int i=n;i>=1;i--)pre[i]=pre[i+1]+z[i][1].w;
	cin>>m;
	for(int i=1;i<=m;i++){
    
		int a=0,prre=0;
		for(int j=1;j<=n;j++){
    
			cin>>a;
			if(!trie[prre].mp.count(id[j][a])){
    
				trie[prre].v.push_back(id[j][a]);
				tot++;
				trie[prre].mp[id[j][a]]=tot;
			}
			prre=trie[prre].mp[id[j][a]];
		}
	}
	for(int i=1;i<=n;i++){
    
		build(i,1,1,num[i]);
	}
	dfs(0,0,0,0);
	stack<int>q;
	int siz=0;
	while(!ans1.empty()){
    
		int a=ans1.top();ans1.pop();
		siz++;
		q.push(a);
	}
	int cnt=0;
	while(!q.empty()){
    
		int a=q.top();q.pop();
		cnt++;
		cout<<z[cnt][a].id<<" ";
	}
	if(ff!=-1&&siz<n){
    
		siz++;
		cout<<z[siz][ff].id<<" ";
	}
	for(int i=siz+1;i<=n;i++)cout<<z[i][1].id<<" ";
	return 0;
}

Ideas Two ：
The title can be seen as , Before enumeration K Big , And not being ban fall , use map+priority_queue and vector Maintain a contour line , Write something like bfs that will do .

Code ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,m;
int num[12];
struct node{
    
	int id,w;
}z[11][200004];
struct nod{
    
	vector<int>v;
	int sum;
	bool operator <(const nod & ths)const{
    
		return sum<ths.sum;
	}
};
priority_queue<nod>q;
map<vector<int>,int>mp1;
map<vector<int>,int>mp2;
vector<int>vv;
bool cmp(node a,node b){
    
	return a.w>b.w;
}
int id[11][200005];
void bfs(){
    
	vv.clear();
	int sum=0;
	for(int i=1;i<=n;i++)vv.push_back(1),sum+=z[i][1].w;
	q.push({
    vv,sum});
	while(!q.empty()){
    
		nod x=q.top();q.pop();
		if(!mp1.count(x.v)){
    
			for(int i=0;i<x.v.size();i++){
    
				cout<<z[i+1][x.v[i]].id<<" ";
			}
			return ;
		}
		for(int i=0;i<x.v.size();i++){
    
			if(x.v[i]==num[i+1])continue;
			int sum=x.sum;
			sum-=z[i+1][x.v[i]].w;
			x.v[i]++;
			sum+=z[i+1][x.v[i]].w;
			if(!mp2.count(x.v)){
    
				mp2[x.v]=1;
				q.push({
    x.v,sum});
			}
			x.v[i]--;
		}
	}
}
int main(){
    
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
    
		cin>>num[i];
		for(int j=1;j<=num[i];j++){
    
			cin>>z[i][j].w;
			z[i][j].id=j;
		}
		sort(z[i]+1,z[i]+1+num[i],cmp);
		for(int j=1;j<=num[i];j++){
    
			id[i][z[i][j].id]=j;
		}
	}
	cin>>m;
	for(int i=1;i<=m;i++){
    
		vv.clear();
		for(int j=1;j<=n;j++){
    
			int a;cin>>a;
			vv.push_back(id[j][a]);
		}
		mp1[vv]=1;
	}
	bfs();
	return 0;
}