QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644559#7626. Quake and RebuildDisplace_WA 296ms5884kbC++142.7kb2024-10-16 14:36:082024-10-16 14:36:08

Judging History

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

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

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=2e5+5;
const int B=500;
int n, m;
int lp[B], rp[B], bid[N];
int fa[N], nxt[N], dis[N];
int dt[B];
inline void rebuild(int i){
	for(int j=lp[i]; j<=rp[i]; ++j){
		int x=j; dis[j]=0;
		while(x>=lp[i]) ++dis[j], x=max(1, fa[x]-dt[i]);
		nxt[j]=x;
	}
}
#define gf(x) (dt[bid[x]]<B?nxt[x]:max(1, fa[x]-dt[bid[x]]))
inline int lca(int x, int y){
	while(gf(x)^gf(y)){
		if(x<y) y=gf(y);
		else x=gf(x);
	}
	while(x^y){
		if(x<y) y=max(1, fa[y]-dt[bid[y]]);
		else x=max(1, fa[x]-dt[bid[x]]);
	}
	return x;
}
inline int dep(int x){
	int ret=0;
	while(x^1){
		if(dt[bid[x]]<B) ret+=dis[x], x=nxt[x];
		else ++ret, x=max(1, fa[x]-dt[bid[x]]);
	}
	return ret;
}
inline int getd(int x, int y){
	if(x==y) return 0;
	return dep(x)+dep(y)-2*dep(lca(x, y));
}
inline bool cmp(int x, int y){
	if(x==y)  return false;
	while(gf(x)^gf(y)){
		if(x<y) y=gf(y);
		else x=gf(x);
	}
	int tem;
	while(x^y){
		if(x<y) {
			tem=max(1, fa[y]-dt[bid[y]]);
			if(tem==x) break;
			else y=tem;
		}
		else {
			tem=max(1, fa[x]-dt[bid[x]]);
			if(tem==y) break;
			else x=tem;
		}
	}
	return x<y;
}
int main(){
	// freopen("D:\\nya\\acm\\B\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\B\\test.out","w",stdout);
	read(n); read(m);
	for(int i=2; i<=n; ++i) read(fa[i]);
	for(int i=2; i<=n; ++i) bid[i]=(i-2)/B+1;
	bid[1]=0; dt[0]=B;
	lp[0]=rp[0]=1;
	for(int i=1; i<=bid[n]; ++i) lp[i]=rp[i-1]+1, rp[i]=rp[i-1]+B;
	rp[bid[n]]=n;
	for(int i=1; i<=bid[n]; ++i) rebuild(i);
	while(m--){
		int op; read(op);
		if(op==1){
			int l, r, d; read(l); read(r); read(d);
			if(bid[l]==bid[r]){
				for(int i=l; i<=r; ++i) fa[i]-=d;
				rebuild(bid[l]);
				continue;
			}
			for(int i=l; i<=rp[bid[l]]; ++i) fa[i]-=d;
			rebuild(bid[l]);
			for(int i=lp[bid[r]]; i<=r; ++i) fa[i]-=d;
			rebuild(bid[r]);
			for(int i=bid[l]+1; i<bid[r]; ++i){
				dt[i]+=d;
				if(dt[i]<B) rebuild(i);
			}
		}
		else{
			int k, x; vector<int> vec;
			read(k);
			while(k--){
				read(x); vec.ep(x);
			}
			sort(vec.begin(), vec.end(), cmp);
			vec.ep(*vec.begin());
			int ans=0;
			for(int i=1; i<(int)vec.size(); ++i) ans+=getd(vec[i-1], vec[i]);
			ans>>=1;
			printf("%d\n", ans+1);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3792kb

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: 5852kb

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: 0
Accepted
time: 280ms
memory: 5884kb

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:

78
78
70
64
60
55
60
58
52
54
51
53
56
51
51
57
55
52
49
55
49
50
53
49
49
48
49
48
53
50
50
54
47
52
45
49
49
46
47
48
49
50
48
49
47
48
47
49
48
50
48
49
48
47
49
48
51
48
48
45
45
46
50
50
50
48
49
46
47
47
46
48
48
47
49
47
46
47
46
47
46
45
47
49
49
50
51
48
48
49
47
47
48
50
46
47
48
50
46
47
...

result:

ok 13214 lines

Test #4:

score: -100
Wrong Answer
time: 296ms
memory: 3916kb

input:

6173 198631
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

2819
1057
1361
831
722
9566
123
624
554
601
241
597
81
29
34
390
350
443
385
9369
9010
258
5
320
27
281
8268
300
8562
322
228
46
271
263
26
268
257
8033
7575
255
258
156
243
270
186
7626
16
13
6600
163
7
35
219
182
214
10
24
23
194
178
188
183
200
167
158
197
24
189
131
35
167
24
189
15
183
176
6894...

result:

wrong answer 2nd lines differ - expected: '1049', found: '1057'