QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#107350	#6103. A+B Problem	bulijiojiodibuliduo^#	AC ✓	251ms	55384kb	C++	2.2kb	2023-05-21 01:52:41	2023-05-21 01:52:44

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-21 01:52:44]
评测

测评结果：AC
用时：251ms
内存：55384kb

查看

[2023-05-21 01:52:41]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=401000;
int p[N],n,t,nxt[N];
VI v[N],son[N];
vector<PII> ans;
int dfs(int u) {
	if (SZ(son[u])==0) {
		v[++t]={u,u,nxt[u]};
		return t;
	} else {
		VI meg;
		for (auto v:son[u]) {
			meg.pb(dfs(v));
		}
		VI pre=v[meg[0]];
		int ps=meg[0];
		if (pre[0]!=pre[1]) {
			v[++t]={u,pre[0],pre[1],pre[2]};
			ans.pb({t,meg[0]});
			ps=t;
		} else {
			v[meg[0]]={u,pre[0],pre[1],pre[2]};
		}
		v[++t]={u,pre[1],pre[2]};
		ans.pb({t,ps});
		int rid=t;
		rep(i,1,SZ(meg)) {
			VI cur=v[meg[i]];
			int ps=meg[i];
			if (cur[0]!=cur[1]) {
				v[++t]={u,cur[0],cur[1],cur[2]};
				ans.pb({t,meg[i]});
				ps=t;
			} else {
				v[meg[i]]={u,cur[0],cur[1],cur[2]};
			}
			v[++t]={u,cur[1],cur[2]};
			ans.pb({t,ps});
			//printf("pre %d %d %d\n",pre[0],pre[1],pre[2]);
			//printf("cur %d %d %d\n",cur[0],cur[1],cur[2]);
			assert(pre[2]==cur[1]);
			v[++t]={u,pre[1],pre[2],cur[2]};
			ans.pb({t,rid});
			ans.pb({t,t-1});
			v[++t]={u,pre[1],cur[2]};
			ans.pb({t,t-1});
			pre=v[t];
			rid=t;
		}
		return rid;
	}
}

int main() {
	scanf("%d",&n);
	//n=100000;
	rep(i,2,n+1) {
		scanf("%d",&p[i]);
		//p[i]=1;
		son[p[i]].pb(i);
	}
	VI lef;
	rep(i,1,n+1) if (son[i].empty()) {
		lef.pb(i);
	}
	rep(i,0,SZ(lef)) nxt[lef[i]]=lef[(i+1)%SZ(lef)];
	dfs(1);
	printf("%d\n",t);
	assert(SZ(ans)==t-1);
	rep(i,1,t+1) {
		set<int> ps(all(v[i]));
		printf("%d ",SZ(ps));
		for (auto x:ps) printf("%d ",x); puts("");
	}
	for (auto [u,v]:ans) printf("%d %d\n",u,v);
}

Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 22472kb

input:

output:

result:

ok partial = 0

Test #2:

score: 0

Accepted

time: 8ms

memory: 22548kb

input:

output:

30
3 1 2 5 
3 4 5 6 
3 4 6 7 
3 4 5 6 
3 4 6 7 
4 4 5 6 7 
3 4 5 7 
3 3 7 9 
4 3 4 5 7 
3 3 5 7 
3 3 7 9 
4 3 5 7 9 
3 3 5 9 
3 8 9 11 
3 2 10 11 
3 2 10 11 
3 8 9 11 
4 2 8 10 11 
3 2 8 11 
4 2 8 9 11 
3 2 8 9 
3 1 2 5 
4 1 3 5 9 
3 1 5 9 
4 1 2 5 9 
3 1 2 9 
4 1 2 8 9 
3 1 2 9 
3 1 2 9 
2 1 2 
4 2...

result:

ok partial = 0

Test #3:

score: 0

Accepted

time: 133ms

memory: 35516kb

input:

output:

200892
3 1 2 93 
3 92 93 842 
3 92 93 842 
4 91 92 93 842 
3 91 93 842 
4 90 91 93 842 
3 90 93 842 
4 89 90 93 842 
3 89 93 842 
4 88 89 93 842 
3 88 93 842 
4 87 88 93 842 
3 87 93 842 
4 86 87 93 842 
3 86 93 842 
4 85 86 93 842 
3 85 93 842 
4 84 85 93 842 
3 84 93 842 
4 83 84 93 842 
3 83 93 8...

result:

ok partial = 0

Test #4:

score: 0

Accepted

time: 148ms

memory: 55384kb

input:

output:

200002
3 1 2 12098 
3 12097 12098 16424 
3 12097 12098 16424 
4 12096 12097 12098 16424 
3 12096 12098 16424 
4 12095 12096 12098 16424 
3 12095 12098 16424 
4 12094 12095 12098 16424 
3 12094 12098 16424 
4 12093 12094 12098 16424 
3 12093 12098 16424 
4 12092 12093 12098 16424 
3 12092 12098 16424...

result:

ok partial = 0

Test #5:

score: 0

Accepted

time: 175ms

memory: 42616kb

input:

output:

318302
3 3 4 7 
3 6 7 12 
3 11 12 13 
3 11 13 16 
3 15 16 18 
3 17 18 22 
3 21 22 24 
3 23 24 26 
3 25 26 28 
3 27 28 36 
3 35 36 41 
3 40 41 43 
3 42 43 49 
3 48 49 51 
3 50 51 56 
3 55 56 59 
3 58 59 66 
3 65 66 71 
3 70 71 77 
3 76 77 81 
3 80 81 83 
3 82 83 86 
3 85 86 88 
3 87 88 92 
3 91 92 94...

result:

ok partial = 0

Test #6:

score: 0

Accepted

time: 176ms

memory: 48672kb

input:

output:

result:

ok partial = 0

Test #7:

score: 0

Accepted

time: 251ms

memory: 39572kb

input:

output:

result:

ok partial = 0

Test #8:

score: 0

Accepted

time: 195ms

memory: 37316kb

input:

output:

281112
3 1 2 4 
3 3 4 7 
3 3 4 7 
3 6 7 11 
3 10 11 14 
3 13 14 16 
3 15 16 19 
3 18 19 24 
3 18 19 24 
4 17 18 19 24 
3 17 19 24 
3 15 16 19 
4 15 17 19 24 
3 15 19 24 
4 15 16 19 24 
3 15 16 24 
3 23 24 31 
3 30 31 32 
3 30 32 33 
3 30 31 32 
3 30 32 33 
4 30 31 32 33 
3 30 31 33 
4 29 30 31 33 
3...

result:

ok partial = 0

Test #9:

score: 0

Accepted

time: 203ms

memory: 36856kb

input:

output:

299482
3 1 2 5 
3 4 5 7 
3 4 5 7 
3 6 7 8 
3 6 8 9 
3 6 9 14 
3 6 7 8 
3 6 8 9 
4 6 7 8 9 
3 6 7 9 
3 6 9 14 
4 6 7 9 14 
3 6 7 14 
3 13 14 15 
3 13 14 15 
3 12 15 16 
3 12 16 17 
4 12 13 14 15 
3 12 14 15 
3 12 15 16 
4 12 14 15 16 
3 12 14 16 
3 12 16 17 
4 12 14 16 17 
3 12 14 17 
4 11 12 14 17 
...

result:

ok partial = 0

Test #10:

score: 0

Accepted

time: 236ms

memory: 36884kb

input:

output:

299978
3 1 2 4 
3 3 4 7 
3 6 7 8 
3 6 8 14 
3 6 7 8 
3 6 8 14 
4 6 7 8 14 
3 6 7 14 
3 13 14 15 
3 13 15 17 
3 13 14 15 
3 13 15 17 
4 13 14 15 17 
3 13 14 17 
3 16 17 18 
3 16 18 21 
3 16 17 18 
3 16 18 21 
4 16 17 18 21 
3 16 17 21 
4 12 13 14 17 
3 12 14 17 
4 12 16 17 21 
3 12 17 21 
4 12 14 17 ...

result:

ok partial = 0

Test #11:

score: 0

Accepted

time: 211ms

memory: 38636kb

input:

output:

378398
3 1 2 4 
3 3 4 5 
3 3 5 8 
3 7 8 9 
3 7 9 10 
3 7 10 11 
3 7 11 12 
3 7 12 13 
3 7 13 14 
3 7 14 16 
3 15 16 17 
3 15 16 17 
3 7 17 18 
3 7 18 20 
3 7 8 9 
3 7 9 10 
4 7 8 9 10 
3 7 8 10 
3 7 10 11 
4 7 8 10 11 
3 7 8 11 
3 7 11 12 
4 7 8 11 12 
3 7 8 12 
3 7 12 13 
4 7 8 12 13 
3 7 8 13 
3 7...

result:

ok partial = 0

Test #12:

score: 0

Accepted

time: 234ms

memory: 39092kb

input:

output:

result:

ok partial = 0

Test #13:

score: 0

Accepted

time: 220ms

memory: 39104kb

input:

output:

397808
3 1 2 4 
3 3 4 5 
3 3 5 6 
3 3 6 7 
3 3 7 8 
3 3 8 9 
3 3 9 10 
3 3 10 11 
3 3 11 12 
3 3 12 13 
3 3 13 14 
3 3 14 15 
3 3 15 16 
3 3 16 17 
3 3 17 18 
3 3 18 19 
3 3 19 20 
3 3 20 21 
3 3 21 22 
3 3 22 23 
3 3 23 24 
3 3 24 25 
3 3 25 26 
3 3 26 27 
3 3 27 28 
3 3 28 29 
3 3 29 30 
3 3 30 31...

result:

ok partial = 0

Test #14:

score: 0

Accepted

time: 187ms

memory: 36976kb

input:

output:

286628
3 7 8 13 
3 12 13 15 
3 12 13 15 
3 14 15 19 
3 18 19 21 
3 18 19 21 
4 17 18 19 21 
3 17 19 21 
3 20 21 22 
3 20 21 22 
3 16 22 23 
4 16 17 19 21 
3 16 19 21 
4 16 20 21 22 
3 16 21 22 
4 16 19 21 22 
3 16 19 22 
3 16 22 23 
4 16 19 22 23 
3 16 19 23 
3 14 15 19 
4 14 16 19 23 
3 14 19 23 
4...

result:

ok partial = 0

Test #15:

score: 0

Accepted

time: 192ms

memory: 37216kb

input:

output:

282148
3 1 2 12 
3 11 12 13 
3 11 13 15 
3 14 15 18 
3 17 18 28 
3 27 28 32 
3 27 28 32 
4 26 27 28 32 
3 26 28 32 
3 31 32 33 
3 31 33 34 
3 31 32 33 
3 31 33 34 
4 31 32 33 34 
3 31 32 34 
4 30 31 32 34 
3 30 32 34 
4 29 30 32 34 
3 29 32 34 
3 25 34 36 
4 25 26 28 32 
3 25 28 32 
4 25 29 32 34 
3...

result:

ok partial = 0

Test #16:

score: 0

Accepted

time: 200ms

memory: 37328kb

input:

output:

273540
3 1 2 52 
3 51 52 72 
3 71 72 82 
3 71 72 82 
4 70 71 72 82 
3 70 72 82 
4 69 70 72 82 
3 69 72 82 
3 81 82 84 
3 81 82 84 
3 83 84 85 
3 83 85 94 
3 83 84 85 
3 83 85 94 
4 83 84 85 94 
3 83 84 94 
3 93 94 97 
3 96 97 100 
3 99 100 106 
3 105 106 114 
3 113 114 121 
3 120 121 130 
3 129 130 ...

result:

ok partial = 0

Test #17:

score: 0

Accepted

time: 198ms

memory: 48080kb

input:

output:

result:

ok partial = 0

Test #18:

score: 0

Accepted

time: 63ms

memory: 28012kb

input:

output:

101256
3 314 315 584 
3 314 315 584 
4 313 314 315 584 
3 313 315 584 
4 312 313 315 584 
3 312 315 584 
4 311 312 315 584 
3 311 315 584 
4 310 311 315 584 
3 310 315 584 
4 309 310 315 584 
3 309 315 584 
4 308 309 315 584 
3 308 315 584 
4 307 308 315 584 
3 307 315 584 
4 306 307 315 584 
3 306 ...

result:

ok partial = 0

Test #19:

score: 0

Accepted

time: 209ms

memory: 49880kb

input:

output:

result:

ok partial = 0

Test #20:

score: 0

Accepted

time: 112ms

memory: 31224kb

input:

output:

181356
3 1 2 7 
3 6 7 10 
3 9 10 12 
3 11 12 18 
3 11 12 18 
3 9 10 12 
4 9 11 12 18 
3 9 12 18 
4 9 10 12 18 
3 9 10 18 
3 17 18 20 
3 17 18 20 
3 19 20 25 
3 19 20 25 
4 16 17 18 20 
3 16 18 20 
4 16 19 20 25 
3 16 20 25 
4 16 18 20 25 
3 16 18 25 
3 24 25 29 
3 24 25 29 
4 23 24 25 29 
3 23 25 29...

result:

ok partial = 0

Test #21:

score: 0

Accepted

time: 136ms

memory: 32048kb

input:

output:

200254
3 8 9 11 
3 10 11 13 
3 10 11 13 
3 8 9 11 
4 8 10 11 13 
3 8 11 13 
4 8 9 11 13 
3 8 9 13 
4 7 8 9 13 
3 7 9 13 
3 12 13 15 
3 12 13 15 
4 6 7 9 13 
3 6 9 13 
4 6 12 13 15 
3 6 13 15 
4 6 9 13 15 
3 6 9 15 
3 14 15 19 
3 18 19 23 
3 22 23 25 
3 22 23 25 
3 24 25 27 
3 26 27 30 
3 26 27 30 
3...

result:

ok partial = 0

Test #22:

score: 0

Accepted

time: 120ms

memory: 31544kb

input:

output:

187028
3 2 3 6 
3 2 3 6 
3 5 6 20 
3 19 20 22 
3 19 20 22 
4 18 19 20 22 
3 18 20 22 
3 21 22 28 
3 21 22 28 
4 17 18 20 22 
3 17 20 22 
4 17 21 22 28 
3 17 22 28 
4 17 20 22 28 
3 17 20 28 
4 16 17 20 28 
3 16 20 28 
4 15 16 20 28 
3 15 20 28 
4 14 15 20 28 
3 14 20 28 
3 27 28 30 
3 29 30 33 
3 29...

result:

ok partial = 0

Test #23:

score: 0

Accepted

time: 137ms

memory: 31192kb

input:

output:

181802
3 8 9 15 
3 14 15 19 
3 14 15 19 
3 18 19 21 
3 20 21 26 
3 25 26 29 
3 25 26 29 
4 24 25 26 29 
3 24 26 29 
4 23 24 26 29 
3 23 26 29 
4 22 23 26 29 
3 22 26 29 
3 20 21 26 
4 20 22 26 29 
3 20 26 29 
4 20 21 26 29 
3 20 21 29 
3 18 19 21 
4 18 20 21 29 
3 18 21 29 
4 18 19 21 29 
3 18 19 29...

result:

ok partial = 0

Test #24:

score: 0

Accepted

time: 119ms

memory: 31116kb

input:

output:

173434
3 38 39 59 
3 58 59 65 
3 64 65 92 
3 91 92 105 
3 104 105 108 
3 107 108 112 
3 111 112 123 
3 122 123 125 
3 122 123 125 
3 124 125 127 
3 126 127 140 
3 126 127 140 
3 124 125 127 
4 124 126 127 140 
3 124 127 140 
4 124 125 127 140 
3 124 125 140 
4 121 122 123 125 
3 121 123 125 
4 121 1...

result:

ok partial = 0

Test #25:

score: 0

Accepted

time: 156ms

memory: 43904kb

input:

output:

result:

ok partial = 0

Test #26:

score: 0

Accepted

time: 180ms

memory: 48996kb

input:

output:

244008
3 15370 15371 15373 
3 15372 15373 15375 
3 15374 15375 15377 
3 15376 15377 15379 
3 15378 15379 15381 
3 15380 15381 15383 
3 15382 15383 15385 
3 15384 15385 15387 
3 15386 15387 15389 
3 15388 15389 15391 
3 15390 15391 15393 
3 15392 15393 15395 
3 15394 15395 15397 
3 15396 15397 15399 ...

result:

ok partial = 0

Test #27:

score: 0

Accepted

time: 151ms

memory: 48268kb

input:

output:

244008
3 9938 9939 9941 
3 9940 9941 9943 
3 9942 9943 9945 
3 9944 9945 9947 
3 9946 9947 9949 
3 9948 9949 9951 
3 9950 9951 9953 
3 9952 9953 9955 
3 9954 9955 9957 
3 9956 9957 9959 
3 9958 9959 9961 
3 9960 9961 9963 
3 9962 9963 9965 
3 9964 9965 9967 
3 9966 9967 9969 
3 9968 9969 9971 
3 997...

result:

ok partial = 0