QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561089#8220. 众生之门robertfan0 3ms7068kbC++142.6kb2024-09-12 20:03:102024-09-12 20:03:11

Judging History

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

  • [2024-09-12 20:03:11]
  • 评测
  • 测评结果：0
  • 用时：3ms
  • 内存：7068kb
查看
  • [2024-09-12 20:03:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math",2,3)
mt19937 rnd(233);
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
const int N=50005;
int tt,n,m,s,t,i,j,lg[50005],dep[50005],dfn[50005],mp[50005],ti,f[16][50005];
vector<int> bi[50005];
void dfs(int x,int fa)
{
	mp[dfn[x]=++ti]=x;f[0][ti]=dep[fa];
	ff(bi[x],it)if(*it!=fa)dep[*it]=dep[x]+1,dfs(*it,x); 
}
int dlca(int x,int y)
{
	if(x==y)return dep[x];x=dfn[x];y=dfn[y];
	if(x>y)swap(x,y);x++;int t=lg[y-x+1];
	return min(f[t][x],f[t][y-(1<<t)+1]); 
}
int dist(int x,int y){return dep[x]+dep[y]-2*dlca(x,y);}

void addedge(int u, int v) { 
	bi[u].push_back(v);
	bi[v].push_back(u);
}

void solve() {
  scanf("%d %d %d", &n, &s,&t);
	for(int i=1;i<=n;i++)bi[i].clear();
  int u, v;
  for (int i = 1; i <= n - 1; ++i) {
    scanf("%d %d", &u, &v);
    addedge(u, v);
  }
//  cout<<e[e[head[28]].nxt].v;
//  return ;;
  vector<int>p(n+2),res(n+2);
  p[1]=s;
  p[n]=t;
  int tot2=1;
  for(int i=1;i<=n;i++)if(i!=s&&i!=t)p[++tot2]=i;
  res=p;
  dfs(1,0);
	fz1(j,lg[n])fz1(i,n-(1<<j)+1) f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
  int nw=200*n,ans=0;
  for(int i=1;i<n;i++)ans^=dist(p[i],p[i+1]);
  if(n>3){
  	int cur=ans;
  	while(ans>1&&(nw--)){
  		int x=rnd()%(n-2)+2;
  		int y=rnd()%(n-3)+2;
  		y+=(y>=x);
  		cur^=dist(p[x],p[x-1]);
  		cur^=dist(p[x],p[x+1]);
  		cur^=dist(p[y],p[y-1]);
  		cur^=dist(p[y],p[y+1]);
  		swap(p[x],p[y]);
  		cur^=dist(p[x],p[x-1]);
  		cur^=dist(p[x],p[x+1]);
  		cur^=dist(p[y],p[y-1]);
  		cur^=dist(p[y],p[y+1]);
  		if(cur<ans)ans=cur,res=p;
	}
  }for(int i=1;i<=n;i++)printf("%d ",res[i]);
  putchar('\n');
  return ;
}
int main(){
	fz(i,2,50000)lg[i]=lg[i/2]+1;
	int t;
	cin>>t;
	while(t--)solve();
}
/*
43 27 2
42 3
30 36
11 24
21 22
13 8
22 30
31 29
35 1
10 6
2 23
28 17
2 26
7 37
5 19
38 43
33 39
4 28
33 7
25 31
15 1
32 18
34 27
35 12
19 32
20 17
37 42
26 34
39 10
12 27
24 43
18 6
16 9
38 9
14 15
14 41
25 3
40 13
16 8
36 41
20 5
21 40
11 29
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 6976kb

input:

114
6 5 6
2 6
1 6
4 5
3 1
6 4
6 3 6
2 4
4 1
6 4
1 5
5 3
6 6 1
5 2
1 2
4 6
2 4
3 2
6 6 1
3 6
5 3
1 6
4 2
2 5
6 3 1
5 3
2 4
1 5
4 3
6 3
4 3 4
2 3
1 4
4 3
6 3 1
2 3
6 3
4 3
1 6
5 1
5 3 2
1 2
4 2
2 3
5 2
6 1 4
2 1
5 2
4 1
6 2
3 6
6 5 1
4 2
6 5
1 3
2 6
3 2
4 4 1
2 4
3 4
1 4
6 2 5
3 5
4 6
1 4
6 2
5 4
6 1 ...

output:

5 1 2 3 4 6 
3 1 2 4 5 6 
6 5 2 4 3 1 
6 2 4 3 5 1 
3 6 5 4 2 1 
3 2 1 4 
3 4 2 6 5 1 
3 4 1 5 2 
1 2 3 5 6 4 
5 3 6 4 2 1 
4 2 3 1 
2 1 3 4 6 5 
1 2 4 5 6 3 
3 6 2 5 4 1 
2 1 3 6 5 4 
3 1 6 2 5 4 
5 1 2 4 6 3 
1 2 3 4 5 
4 1 3 2 
3 5 1 2 4 
1 2 3 4 
3 4 1 2 
5 3 1 4 2 
5 2 3 4 1 
5 1 2 4 6 3 
4 1 6...

result:

wrong answer Your solution is worse than Jury's in test case 3. Yours:3 Jury's:1

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

14190
43 27 2
42 3
30 36
11 24
21 22
13 8
22 30
31 29
35 1
10 6
2 23
28 17
2 26
7 37
5 19
38 43
33 39
4 28
33 7
25 31
15 1
32 18
34 27
35 12
19 32
20 17
37 42
26 34
39 10
12 27
24 43
18 6
16 9
38 9
14 15
14 41
25 3
40 13
16 8
36 41
20 5
21 40
11 29
41 24 38
21 6
20 14
26 1
6 7
17 16
39 36
8 18
36 11...

output:

27 17 35 34 25 13 6 31 37 9 24 14 4 28 19 16 22 39 11 20 21 29 18 36 15 10 1 26 42 33 41 8 3 32 30 7 38 40 5 12 23 43 2 
24 2 1 11 4 21 6 18 9 8 25 20 12 28 30 15 16 40 39 19 3 5 22 23 13 26 27 10 29 36 17 32 33 34 35 14 37 7 31 41 38 
5 9 27 3 4 6 12 8 1 13 11 15 10 14 7 24 23 18 21 20 19 17 16 25 ...

result:

Subtask #4:

score: 0
Runtime Error

Test #18:

score: 0
Runtime Error

input:

32752
15 3 4
14 12
4 12
1 10
9 13
7 6
12 5
1 12
9 15
7 9
8 12
2 6
11 6
9 3
6 10
13 12 2
10 11
10 5
1 4
12 11
4 6
2 13
6 5
9 6
8 13
6 3
4 8
13 7
15 3 6
15 10
4 2
8 5
10 3
1 3
15 2
8 4
12 9
7 8
11 8
6 13
8 12
14 8
6 12
15 5 7
8 14
10 13
11 13
13 5
2 14
15 8
15 1
6 2
7 15
9 13
15 3
6 13
15 4
12 5
15 10...

output:

3 1 2 5 6 7 8 9 10 11 12 13 14 15 4 
12 1 3 4 5 10 7 8 9 13 11 6 2 
3 1 8 2 15 10 12 7 11 5 9 4 13 14 6 
5 15 2 3 10 11 8 4 13 6 12 9 14 1 7 
10 7 9 14 4 1 2 13 5 15 6 12 11 3 8 
11 1 2 4 5 6 7 8 9 10 3 
11 1 10 3 13 5 6 7 8 2 12 4 14 15 9 
14 1 2 3 4 7 6 5 8 9 10 11 13 12 
5 11 2 4 6 8 1 10 7 9 3 
...

result:

Subtask #5:

score: 0
Runtime Error

Test #25:

score: 0
Runtime Error

input:

36059
13 9 4
5 9
10 3
3 1
13 5
12 5
7 4
2 8
8 10
4 9
11 7
6 11
1 4
13 12 6
4 12
13 9
11 2
6 12
9 12
8 5
7 6
5 3
3 7
10 8
1 5
2 10
13 10 8
3 1
5 9
4 8
6 11
7 13
13 5
1 10
12 13
9 4
11 9
2 11
8 10
12 1 4
9 2
2 12
3 2
12 11
8 2
7 4
5 1
4 1
11 7
10 9
6 9
13 10 12
7 5
11 9
12 10
9 8
3 10
8 5
4 13
13 7
6 ...

output:

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

result:

Subtask #6:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 3ms
memory: 7068kb

input:

10
1000 165 244
175 661
738 362
280 462
776 922
231 578
963 615
639 836
32 418
519 220
565 733
239 951
768 847
196 200
246 119
591 288
994 586
313 46
971 515
512 811
228 908
627 339
33 337
447 488
616 319
399 727
921 615
421 509
167 354
905 382
20 356
875 414
619 904
824 940
435 244
953 663
719 962
...

output:

165 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 100 101 ...

result:

wrong answer Your solution is worse than Jury's in test case 2. Yours:7 Jury's:1

Subtask #7:

score: 0
Skipped

Dependency #2:

0%
English 繁體中文 简体中文

Server Time: 2024-12-05 08:30:04 | OpenSource Project