QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#642478	#9373. Query on Tree	IllusionaryDominance	ML	0ms	18096kb	C++20	10.2kb	2024-10-15 14:29:30	2024-10-15 14:29:34

Judging History

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

[2024-10-15 14:29:34]
评测

测评结果：ML
用时：0ms
内存：18096kb

查看

[2024-10-15 14:29:30]
提交

answer

#include <bits/stdc++.h>

template <class T>
inline int qlog(T a) {
    if (!a) return 0;
	double x = a;
	return ((*(long long*) & x) >> 52 & 2047) - 1023;
}

#define cin Mizuhashi
#define cout Parsee
#define endl '\n'

class Reader{
	private:
	    static const int BUF_SIZE = 1 << 22;
	    char BUF_R[BUF_SIZE], *csy1, *csy2;
	    #ifndef _LOCAL_RUNNING
		    #define GC (csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2) ? EOF : *csy1 ++)
		#else
		    char cur;
		    #define GC (cur = getchar())
		#endif
	    #define IL inline
		
    public:
        IL bool eof() {
            #ifndef _LOCAL_RUNNING
                return csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2);
            #else
                return cur == EOF;
            #endif
        }
        template <class Ty>
        IL Reader& operator >> (Ty &t) {
            int u = 0;
            char c = GC;
	    	for (t = 0; c < 48 || c > 57; c = GC)
                if (c == EOF) break;
                else if (c == '-') u = 1;
	    	for ( ; c > 47 && c < 58; c = GC) t = (t << 1) + (t << 3) + (c ^ 48);
	    	t = u ? -t : t; return *this;
        }
    	IL Reader& operator >> (double &t) {
            int tmp, u = 0; char c = GC;
	    	for (tmp = 0; c < 48 || c > 57; c = GC)
                if (c == EOF) break;
                else if (c == '-') u = 1;
	    	for ( ; c > 47 && c < 58; c = GC) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48);
	    	t = (tmp = u ? -tmp : tmp);
    	    if (c == '.') {
    	        double x = 1;
    	        for (c = GC; c > 47 && c < 58; c = GC) t += (x /= 10) * (c ^ 48);
    	    }
    	    return *this;
    	}
    	IL Reader& operator >> (char *s) {
			char c = GC;
			for (*s = 0; c < 33; c = GC) if (c == EOF) return *this;
			for ( ; c > 32; c = GC) *s ++ = c;
			*s = 0; return *this;
		}
        IL Reader& operator >> (char &c) {
			for (c = GC; c < 33; c = GC) if (c == EOF) return *this;
            return *this;
        }
}cin;
class Writer{
	private:
	    static const int BUF_SIZE = 1 << 22;
	    char BUF_W[BUF_SIZE], *csy;
	    #define IL inline
		inline void WC(const char c) {
			if (csy - BUF_W == BUF_SIZE) fwrite(BUF_W, 1, BUF_SIZE, stdout), csy = BUF_W;
			*csy ++ = c;
		}
	
	public:
		Writer() : csy(BUF_W) {}
		~ Writer() {fwrite(BUF_W, 1, csy - BUF_W, stdout);}
		IL void flush() {fwrite(BUF_W, 1, csy - BUF_W, stdout); csy = BUF_W;}
		template <class Ty>
		IL Writer& operator << (Ty x) {
		    static int sta[32], top;
			if (x < 0) {
				WC('-');
                do sta[top ++] = - (x % 10); while (x /= 10);
			}else do sta[top ++] = x % 10; while (x /= 10);
			while (top) WC(sta[-- top] ^ 48);
			return *this;
		}
		IL Writer& operator << (const char &c) {WC(c); return *this;}
		IL Writer& operator << (const char *s) {while (*s) WC(*s ++); return *this;}
		IL Writer& operator << (char *s) {while (*s) WC(*s ++); return *this;}
}cout;

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef vector <int> vi;
typedef vector <ll> vl;

void init();

const int MAX_N = 200000 + 5;
const int MAX_M = MAX_N * 10;
const int INF32 = 0x3f3f3f3f;
const ll INF64 = 0x1f1f1f1f1f1f1f1fll;
const ll threshold = -1e16;
const int P = 998244353;
const int K = 9;

int N, Q;
ll a[MAX_N];
struct Edge{
	int y, prev;
}e[MAX_N << 1];
int elast[MAX_N], ecnt;
int fa[MAX_N], dep[MAX_N], bfsn[MAX_N], cnt[MAX_N], dfsn[MAX_N][2], Tm;
pii seg[MAX_N][K + 1];
vl b[MAX_N];
struct SegmentNode{
	int ls, rs;
	ll maxv, lazy;
	
	void clear() {
		ls = 0;
		rs = 0;
		maxv = -INF64;
		lazy = 0;
	}
}node[MAX_M];
int rt[MAX_N], tot;

inline int NewNode() {
	tot ++;
	node[tot].clear();
	return tot;
}

void segment_build(int &i, int l, int r, int d) {
	i = NewNode();
	if (l == r) {
		node[i].maxv = b[d][l];
		return ;
	}
	int mid = l + r >> 1;
	segment_build(node[i].ls, l, mid, d);
	segment_build(node[i].rs, mid + 1, r, d);
	node[i].maxv = max(node[node[i].ls].maxv, node[node[i].rs].maxv);
}

ll segment_modify(int i, int l, int r, int ql, int qr, int v) {
	if (l < ql || r > qr) {
		ll res = -INF64;
		int mid = l + r >> 1;
		if (ql <= mid) res = segment_modify(node[i].ls, l, mid, ql, qr, v);
		if (mid < qr) res = max(res, segment_modify(node[i].rs, mid + 1, r, ql, qr, v));
		node[i].maxv = max(node[node[i].ls].maxv, node[node[i].rs].maxv) + node[i].lazy;
		return res + node[i].lazy;
	}else {
		node[i].maxv += v;
		node[i].lazy += v;
		return node[i].maxv;
	}
}

ll segment_query(int i, int l, int r, int ql, int qr) {
	if (qr < ql) return -INF64;
	if (l < ql || r > qr) {
		ll res = -INF64;
		int mid = l + r >> 1;
		if (ql <= mid) res = segment_query(node[i].ls, l, mid, ql, qr);
		if (mid < qr) res = max(res, segment_query(node[i].rs, mid + 1, r, ql, qr));
		return res + node[i].lazy;
	}else {
		return node[i].maxv;
	}
}

void segment_assign(int i, int l, int r, int x, ll v, ll sum = 0) {
	if (l == r) {
		node[i].maxv = v - sum;
		node[i].lazy = 0;
		return ;
	}
	sum += node[i].lazy;
	int mid = l + r >> 1;
	mid < x ? segment_assign(node[i].rs, mid + 1, r, x, v, sum) : segment_assign(node[i].ls, l, mid, x, v, sum);
	node[i].maxv = max(node[node[i].ls].maxv, node[node[i].rs].maxv) + node[i].lazy;
}

inline pii operator + (const pii &a, const pii &b) {
	return pair(min(a.first, b.first), max(a.second, b.second));
}

inline pii& operator += (pii &a, const pii &b) {
	a.first = min(a.first, b.first);
	a.second = max(a.second, b.second);
	return a;
}

void Build(int x, int y) {
	ecnt ++;
	e[ecnt].y = y;
	e[ecnt].prev = elast[x];
	elast[x] = ecnt;
}

void dfs(int u, int fath) {
	fa[u] = fath;
	dep[u] = dep[fath] + 1;
	dfsn[u][0] = ++ Tm;
	bfsn[u] = ++ cnt[dep[u]];
	seg[u][0] = pair(bfsn[u], bfsn[u]);
	for (int j = 1; j <= K; j ++) seg[u][j] = pair(N, 0);
	for (int i = elast[u]; i; i = e[i].prev) {
		int v = e[i].y;
		if (v != fath) {
			dfs(v, u);
			for (int j = 1; j <= K; j ++) seg[u][j] += seg[v][j - 1];
		}
	}
}

pair <pii, pii> operator - (const pii &a, const pii &b) {
	assert(a.first <= b.first && b.first <= b.second && b.second <= a.second);
	return pair(pair(a.first, b.first - 1), pair(b.second + 1, a.second));
}

ll modify1(int u, int k, int v) {
	static int anc[K + 1];
	anc[0] = u;
	for (int i = 1, j = fa[u]; i <= k; i ++, j = fa[j]) anc[i] = j;
	ll res = -INF64;
	if (cnt[dep[u] + k]) {
		auto [l, r] = seg[u][k];
		res = segment_modify(rt[dep[u] + k], 1, cnt[dep[u] + k], l, r, v);
	}
	for (int i = 1; i < k; i ++) {
		if (!anc[i]) break;
		auto [seg1, seg2] = seg[anc[i]][k - i] - seg[anc[i - 1]][k - i - 1];
		auto [l1, r1] = seg1; auto [l2, r2] = seg2; int d_ = dep[u] + k - (i << 1);
		if (l1 <= r1) {
			res = max(res, segment_modify(rt[d_], 1, cnt[d_], l1, r1, v));
		}
		if (l2 <= r2) {
			res = max(res, segment_modify(rt[d_], 1, cnt[d_], l2, r2, v));
		}
	}
	if (anc[k]) {
		res = max(res, segment_modify(rt[dep[u] - k], 1, cnt[dep[u] - k], bfsn[anc[k]], bfsn[anc[k]], v));
	}
	if (res > threshold) {
		for (int i = k; i < K; i ++) u = fa[u];
		for (int i = 1; i <= k; i ++) {
			if (!u) break;
			auto [l, r] = seg[u][K];
			if (l <= r) {
				segment_assign(rt[0], 1, N, dfsn[u][0], segment_query(rt[dep[u] + K], 1, cnt[dep[u] + K], l, r));
			}
			u = fa[fa[u]];
		}
	}
	return res;
}

ll modify2(int u, int k, int v) {
	ll res = -INF64;
	static pii mdf[K << 1 | 1];
	for (int i = 0; i <= (k << 1); i ++) mdf[i] = pair(N, 0);
	for (int i = 0, x = u; i <= k; i ++, x = fa[x]) {
		if (!x) break;
		for (int j = 0; j <= k - i; j ++) {
			mdf[k - i + j] += seg[x][j];
		}
	}
	for (int i = 0; i <= (k << 1); i ++) {
		auto [l, r] = mdf[i];
		if (l <= r) {
			int d_ = dep[u] - k + i;
			res = max(res, segment_modify(rt[d_], 1, cnt[d_], l, r, v));
		}
	}
	for (int i = k; i < K; i ++) u = fa[u];
	for (int i = 0; i <= (k << 1); i ++) {
		if (!u) break;
		auto [l, r] = seg[u][K];
		if (l <= r) {
			segment_assign(rt[0], 1, N, dfsn[u][0], segment_query(rt[dep[u] + K], 1, cnt[dep[u] + K], l, r));
		}
		u = fa[u];
	}
	return res;
}

ll modify3(int u, int v) {
	ll res = -INF64;
	for (int i = 0; i <= K; i ++) {
		auto [l, r] = seg[u][i];
		if (r < l) break;
		res = max(res, segment_modify(rt[dep[u] + i], 1, cnt[dep[u] + i], l, r, v));
	}
	for (int i = 0, x = u; i <= K; i ++, x = fa[x]) {
		if (!x) break;
		auto [l, r] = seg[x][K];
		if (l <= r) {
			segment_assign(rt[0], 1, N, dfsn[x][0], segment_query(rt[dep[x] + K], 1, cnt[dep[x] + K], l, r));
		}
	}
	res = max(res, segment_modify(rt[0], 1, N, dfsn[u][0], dfsn[u][1], v));
	return res;
}

void solve() {
	ecnt = 0; Tm = 0; tot = 0;
	memset(rt, 0, sizeof(int) * (N + 1));
	memset(cnt, 0, sizeof(int) * (N + 1));
	memset(elast, 0, sizeof(int) * (N + 1));
	
	cin >> N >> Q;
	for (int i = 1; i <= N; i ++) cin >> a[i];
	for (int i = 1; i < N; i ++) {
		int x, y;
		cin >> x >> y;
		Build(x, y);
		Build(y, x);
	}
	dfs(1, 0);
	for (int i = 1; i <= N; i ++) {
		if (cnt[i]) {
			b[i].resize(cnt[i] + 1);
		}
	}
	for (int i = 1; i <= N; i ++) {
		b[dep[i]][bfsn[i]] = a[i];
	}
	for (int i = 1; i <= N; i ++) {
		if (cnt[i]) {
			segment_build(rt[i], 1, cnt[i], i);
		}
	}
	b[0].resize(N + 1);
	for (int i = 1; i <= N; i ++) {
		auto [l, r] = seg[i][K];
		if (l <= r) {
			b[0][dfsn[i][0]] = segment_query(rt[dep[i] + K], 1, cnt[dep[i] + K], l, r);
		}else {
			b[0][dfsn[i][0]] = -INF64;
		}
	}
	segment_build(rt[0], 1, N, 0);
	
	for (int i = 1; i <= Q; i ++) {
		int opt, x, k, v;
		cin >> opt >> x >> k;
		ll res = 0;
		if (opt == 1) {
			cin >> v;
			res = modify1(x, k, v);
		}else if (opt == 2) {
			cin >> v;
			res = modify2(x, k, v);
		}else {
			assert(opt == 3);
			res = modify3(x, k);
		}
		if (res > threshold) {
			cout << res << endl;
		}else {
			cout << "GG\n";
		}
	}
}

int main() {
	init();
    int T = 1;
    cin >> T;
    while (T --) solve();
	cerr << clock() << endl;
    return 0;
}

void init() {
	srand(time(0));
	for (int i = 0; i < 1e9; i += rand());
}

/*
1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1
*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 18096kb

input:

output:

result:

ok 5 lines

Test #2:

score: -100

Memory Limit Exceeded

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
1 3
1 2
1 1 5 -71952967
3 1 -816873082
1 1 5 -842437577
2 3 7 254550528
3 3 -854082700
2 3 2 699808309
3 3 554885567
1 2 7 595565507
1 3 0 -318374053
3 2
-63158159333100 77264362049163 -99188430131116
1 2
3 2
2 2 4 -305866230
3 1 -549738403
3 5...