QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#166944#6742. LeavesPhantomThreshold#WA 1ms3500kbC++202.8kb2023-09-06 21:24:132023-09-06 21:24:13

Judging History

你现在查看的是最新测评结果

  • [2023-09-06 21:24:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3500kb
  • [2023-09-06 21:24:13]
  • 提交

answer

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

const int maxn=1000;
int n,m;
int a[maxn+5];
int g[maxn+5][2];
int sz[maxn+5];
int nonleaf[maxn+5];

pair<int,int> dp[maxn+5][maxn/2+5];

int top=0;
int arr[maxn+5];
void getarray(int u,int t){
//	cerr << u << " " << t << " " << top << endl;
	if (sz[u]==0){
		arr[++top]=a[u];
		return;	
	}
	int flip=dp[u][t].second;
	int v=g[u][0];
	int w=g[u][1];
	int vt=dp[u][t].first;
	int wt=t-vt-flip;
	if (!flip){
		getarray(v,vt);
		getarray(w,wt);
	}
	else{
		getarray(w,wt);
		getarray(v,vt);	
	}
}

int nowtop=0;
int nowarr[maxn+5];

void dfs(int u){
	nonleaf[u]=1;
	if (sz[u]==0){
		nonleaf[u]=0;
		dp[u][0]=make_pair(0,0);
		return;
	}
	int v=g[u][0];
	int w=g[u][1];
	dfs(v);
	dfs(w);
	nonleaf[u]+=nonleaf[v];
	nonleaf[u]+=nonleaf[w];
	for (int t=0;t<=nonleaf[u] && t<=m;t++){
		for (int flip=0;flip<=1;flip++){
			for (int vt=0;vt<=nonleaf[v] && vt<=t-flip;vt++){
				if (dp[v][vt].first==-1) continue;
				if (!flip){
					top=0;
					getarray(v,vt);
					getarray(w,t-flip-vt);	
				}
				else{
					top=0;
					getarray(w,t-flip-vt);
					getarray(v,vt);
				}
				if (dp[u][t].first==-1){
					dp[u][t]=make_pair(vt,flip);
					nowtop=top;
					for (int i=1;i<=top;i++) nowarr[i]=arr[i];
				}
				else{
					bool flag=0;
					for (int i=1;i<=top;i++){
						if (arr[i]==nowarr[i]) continue;
						if (arr[i]<nowarr[i]) flag=1;
						break;
					}
					if (flag){
						dp[u][t]=make_pair(vt,flip);
						nowtop=top;
						for (int i=1;i<=top;i++) nowarr[i]=arr[i];	
					}
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	
	cin >> n >> m;
	for (int i=1;i<=n;i++){
		int opt=0;
		cin >> opt;
		if (opt==1){
			int x,y;
			cin >> x >> y;
			sz[i]=2;
			g[i][0]=x;
			g[i][1]=y;
		}
		else{
			cin >> a[i];
			sz[i]=0;	
		}
	}
	/*
	cerr << "---" << endl;
	for (int i=1;i<=n;i++) cerr << sz[i] << " ";
	cerr << endl;
	for (int i=1;i<=n;i++) cerr << g[i][0] << " " << g[i][1] << endl;
	for (int i=1;i<=n;i++) cerr << a[i] << " ";
	cerr << endl;
	cerr << "---" << endl;
	*/
	for (int i=1;i<=n;i++)
		for (int j=0;j<=m;j++) dp[i][j]=make_pair(-1,-1);
		
	dfs(1);
	/*
	for (int i=1;i<=n;i++){
		for (int j=0;j<=2;j++){
			cerr << "(" << dp[i][j].first << "," << dp[i][j].second << ") ";
		}
		cerr << endl;
	}
	*/
	nowtop=n;
	for (int i=1;i<=nowtop;i++) nowarr[i]=n+1;
	
	for (int t=m;t>=0;t-=2){
		if (dp[1][t].first==-1) continue;
	//	cerr << "-------------" << endl;
		top=0;
		getarray(1,t);
		bool flag=0;
		for (int i=1;i<=top;i++){
			if (arr[i]==nowarr[i]) continue;
			if (arr[i]<nowarr[i]) flag=1;
			break;
		}
		if (flag){
			nowtop=top;
			for (int i=1;i<=top;i++) nowarr[i]=arr[i];	
		}	
	}
	for (int i=1;i<=nowtop;i++) cout << nowarr[i] << " \n"[i==nowtop];
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3444kb

input:

3 0
1 2 3
2 1
2 2

output:

1 2

result:

ok 2 number(s): "1 2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

7 1
1 2 3
1 4 5
1 6 7
2 4
2 2
2 3
2 1

output:

2 4 3 1

result:

ok 4 number(s): "2 4 3 1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

7 2
1 2 3
1 4 5
1 6 7
2 4
2 2
2 3
2 1

output:

1 3 4 2

result:

ok 4 number(s): "1 3 4 2"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3464kb

input:

1 0
2 1000000000

output:

2

result:

wrong answer 1st numbers differ - expected: '1000000000', found: '2'