QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129171#6742. LeavesjeffqiWA 1ms3540kbC++232.2kb2023-07-22 04:21:322023-07-22 04:21:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-22 04:21:34]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3540kb
  • [2023-07-22 04:21:32]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ull unsigned ll
#define i128 __int128
using namespace std;
namespace qiqi {
	void main() {
		int n,m;
		cin >> n >> m;
		vi a(n),siz(n);
		vector<array<int,2>> ch(n,{-1,-1});
		for (int i = 0; i < n; i++) {
			int c; cin >> c;
			if (c == 1) {
				for (int j = 0; j < 2; j++) {
					cin >> ch[i][j]; ch[i][j]--;
				}
			}
			else {
				cin >> a[i];
			}
		}
		auto dfs = [&](auto self,int u) -> vector<vi> {
			if (ch[u] == array<int,2>{-1,-1}) {
				siz[u] = 1;
				return vector<vi>({vi({a[u]})});
			}
			else {
				vector<vi> v[2];
				for (int i = 0; i < 2; i++) {
					v[i] = self(self,ch[u][i]);
					siz[u] += siz[ch[u][i]];
				}
				vector<vi> vec(siz[u]);
				for (int j = 0; j < 2; j++) {
					for (int k = 0,p = 0; k < 2; k++,p = k) {
						for (int i = p; i+j < siz[u]; i++) {
							while (i-p >= sz(v[j^1])) {
								p += 2;
							}
							if (p < sz(v[j]) && p < i && !v[j][p].empty() && !v[j^1][i-p].empty()) {
								int cur = (i-k)/2*2+k;
								if (cur < sz(v[j]) && v[j][cur] < v[j][p]) {
									p = cur;
								}
								vi tmp = v[j][p];
								tmp.insert(tmp.end(),all(v[j^1][i-p]));
								if (vec[i+j].empty() || vec[i+j] > tmp) {
									vec[i+j] = tmp;
								}
							}
						}
					}
				}
				for (int i = 2; i < siz[u]; i++) {
					if (vec[i].empty() || vec[i] > vec[i-2]) {
						vec[i] = vec[i-2];
					}
				}
				return vec;
			}
		};
		auto vec = dfs(dfs,0)[m];
		for (auto x:vec) {
			cout << x << ' ';
		}
		cout << '\n';
	}
}
int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	qiqi::main();
//	cout << (double)(clock()-st)/CLOCKS_PER_SEC;
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3540kb

input:

3 0
1 2 3
2 1
2 2

output:



result:

wrong answer Answer contains longer sequence [length = 2], but output contains 0 elements