D. Gellyfish and Camellia Japonica【Codeforces Round 1028 (Div. 2)】

D. Gellyfish and Camellia Japonica

思路

贪心+构造（其实是思维题）
先找必要性，再验证充分性：
倒着求出每个位置的下界作为这个位置的值，再正着验证构造出的这个数列是否合法。
代码非常短，这个题如果当时想出来就上大分了，可惜了。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5 + 5, MAXN = maxn;
int x[maxn], y[maxn], z[maxn];
void solve() {int n, q;cin >> n >> q;vector<int> b(n + 1);for (int i = 1; i <= n; i++) {cin >> b[i];}for (int i = 1; i <= q; i++) {cin >> x[i] >> y[i] >> z[i];}vector<int> a = b;for (int i = q; i >= 1; i--) { // 逆向最小化贪心构造a[x[i]] = max(a[x[i]], a[z[i]]);a[y[i]] = max(a[y[i]], a[z[i]]);if (z[i] != x[i] && z[i] != y[i]) {a[z[i]] = 0; // z只由x、y决定，取最小值0}}vector<int> c = a;for (int i = 1; i <= q; i++) { // 正向模拟验证c[z[i]] = min(c[x[i]], c[y[i]]);}if (c != b) {cout << "-1\n";} else {for (int i = 1; i <= n; i++) {cout << a[i] << " ";}cout << endl;}
}signed main() {
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifcin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}