QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642424#7626. Quake and RebuildfryanWA 202ms3864kbC++173.8kb2024-10-15 14:08:082024-10-15 14:08:08

Judging History

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

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2024-10-15 14:08:08]
  • 评测
  • 测评结果:WA
  • 用时:202ms
  • 内存:3864kb
  • [2024-10-15 14:08:08]
  • 提交

answer

#pragma once
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mxn = 2e5+5;
const int bsz = 400; //change
const int nbk = 400;

int n,m;
int fa[mxn];
int nx[mxn];
int dx[mxn];
int lz[nbk];

inline int nex(int v) {
	if (lz[v/bsz] >= bsz) {
		return max(fa[v]+lz[v/bsz],0);
	}
	return nx[v];
}

inline int dex(int v) {
	if (lz[v/bsz] >= bsz) {
		return 1;
	}
	return dx[v];
}

inline void manual_update(int v) {
	int f = max(fa[v]+lz[v/bsz],0);
	if (f/bsz != v/bsz) {
		nx[v] = f;
		dx[v] = dx[f]+1;
	} else {
		nx[v] = nex(f);
		dx[v] = 1;
	}
}

int lca(int a, int b) {
	while (1) {
		if (a < b) swap(a,b);
		//a > b
		int na = nex(a);
		int nb = nex(b);
		if (na != nb) {
			a = na;
		} else {
			break;
		}
	}
	while (1) {
		if (a==b) return a;
		if (a < b) swap(a,b);
		a = max(fa[a]+lz[a/bsz],0);
	}
	exit(1);
}

void quake(int l, int r, int d) {
	for (int i=l; i%bsz && i<=r; i++) {
		fa[i] -= d;
		manual_update(i);
	}
	
	int lb = (l+bsz-1)/bsz;
	int rb = r/bsz-1;
	for (int i=lb; i<=rb; i++) {
		lz[i] -= d;
		if (-lz[i] < bsz) {
			//manual update
			for (int j=i*bsz; j<(i+1)*bsz; j++) {
				manual_update(j);
			}
		}
	}
	//do right update
	if (r/bsz != l/bsz) {
		for (int i=bsz*(r/bsz); i<=r; i++) {
			fa[i] -= d;
			manual_update(i);
		}
	}
}

int vis[mxn];
int vnx[mxn];
int ans;
vector<int> proc[nbk];
vector<int> rem, rnx, vcl;

void manual_up(int v) {
	int sbk = v/bsz;
	while (v/bsz == sbk && !vis[v]) {
		vis[v] = 1; rem.push_back(v);
		ans++;
		v = max(fa[v]+lz[v/bsz],0);
	}
}

void rebuild_smart(vector<int> &val) {
	rem.clear();
	for (int i=0; i<nbk; i++) {
		proc[i].clear();
	}
	sort(all(val));
	val.erase(unique(all(val)),val.end());
	int RT = val[0];
	for (int i=1; i<sz(val); i++) {
		RT = lca(RT,val[i]);
	}
	ans = 1;
	vis[RT] = 1;
	rem.push_back(RT);
	for (int i : val) {
		proc[i/bsz].push_back(i);
	}
	for (int i = (n+bsz-1)/bsz; i>=0; i--) {
		rnx.clear(); vcl.clear();
		int flag = 0;
		for (int v : proc[i]) {
			if (vis[v]) continue;
			vis[v] = 1;
			vcl.push_back(v);
			int nxx = nex(v);
			vnx[nxx]++;
			rnx.push_back(nex(v));
			if (vnx[nxx]==2) {flag = 1; break;}
		}
		if (i == RT/bsz) flag = 1;
		for (auto v : rnx) {vnx[v] = 0;}
		for (auto v : vcl) {vis[v] = 0;}
		if (flag) {
			for (int v : proc[i]) {
				manual_up(v);
			}
		} else {
			for (int v : proc[i]) {
				if (vis[v]) continue;
				vis[v] = 1;
				ans += dex(v);
				proc[i-1].push_back(nex(v));
			}
		}
	}
	for (int i : rem) vis[i] = 0;
	cout<<ans<<"\n";
}

void rebuild(vector<int> &val) {
	set<int> ans;
	sort(all(val));
	val.erase(unique(all(val)),val.end());
	for (int i=0; i<sz(val); i++) {
		for (int j=i+1; j<sz(val); j++) {
			int R = lca(val[i],val[j]);
			int v = val[i];			
			ans.insert(R);
			while (v != R) {
				ans.insert(v);
				v = max(fa[v]+lz[v/bsz],0);
			}
			v = val[j];
			while (v != R) {
				ans.insert(v);
				v = max(fa[v]+lz[v/bsz],0);
			}
		}
	}
	cout<<sz(ans)<<"\n";
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>m;
	
	for (int i=1; i<n; i++) {
		cin>>fa[i]; --fa[i];
	}
	
	//build nx
	for (int i=0; i<n; i++) {
		if (fa[i]/bsz == i/bsz) {
			nx[i] = nx[fa[i]];
			dx[i] = dx[fa[i]]+1;
		} else {
			nx[i] = fa[i];
			dx[i] = 1;
		}
	}
	
	while (m--) {
		int t; cin>>t;
//		cout<<t<<endl;
		if (t==1) {
			//quake
			int l,r,d; cin>>l>>r>>d;
			quake(l-1,r-1,d);
		} else {
			int k; cin>>k;
			vector<int> val;
			for (int i=0; i<k; i++) {
				int x; cin>>x; --x;
				val.push_back(x);
			}
//			rebuild(val);
//			cout<<flush;
			rebuild_smart(val);
//			cout<<"\n";
		}
	}
	
	return 0;
}

详细

Test #1:

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

input:

4 5
1 2 2
2 2 1 4
1 2 3 1
2 3 2 3 4
1 4 4 1
2 2 3 4

output:

3
4
3

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3

output:

10
3
3

result:

ok 3 lines

Test #3:

score: -100
Wrong Answer
time: 202ms
memory: 3704kb

input:

3051 198219
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...

output:

74
86
78
61
65
51
59
50
48
51
44
50
54
46
48
59
58
45
46
47
47
51
56
51
48
47
45
52
52
54
42
58
49
49
46
49
48
46
46
44
50
43
43
44
44
41
46
52
49
48
51
43
46
43
51
47
40
46
45
44
42
47
44
49
42
44
43
45
40
41
45
46
44
45
42
41
46
45
45
49
45
44
48
46
46
48
44
45
45
46
44
43
40
41
43
45
43
39
44
43
...

result:

wrong answer 1st lines differ - expected: '78', found: '74'