Submission #19422169


Source Code Expand

Copy
#include <cstdio>
#define reg register
#define min(_a,_b) (_a<_b?_a:_b)
const int N=100002;
int fir[N],d[N],fa[N],nex[N<<1],to[N<<1],s1[N],s2[N],st[N],tot,tl,sum,top,ed;
bool vis[N];
int R()
{
	reg int x=0; reg bool f=0; reg char ch=getchar();
	for(;ch<48||ch>57;ch=getchar()) f|=ch=='-';
	for(;ch>=48&&ch<=57;ch=getchar()) x=x*10+ch-48;
	return f?-x:x;
}
void add(reg int u,reg int v)
{
	nex[++tot]=fir[u],fir[u]=tot,to[tot]=v,++d[u]; 
}
void dfs(reg int u,reg int dis)
{
	if(dis>sum) sum=dis,ed=u;
	for(reg int i=fir[u];i;i=nex[i])
		if(to[i]!=fa[u]) fa[to[i]]=u,dfs(to[i],dis+1);
}
int main()
{
	reg int n=R(),i,j,u,v,now,cmp=0;
	for(i=1;i<n;++i) {
		u=R(),v=R();
		add(u,v),add(v,u);
	}
	fa[1]=0,dfs(1,0);
	u=ed;
	sum=fa[u]=0,dfs(u,0);
	v=ed;
	for(i=v;i!=u;i=fa[i]) st[++top]=i,vis[i]=1;
	st[++top]=u,vis[u]=1,tot=tl=0;
	for(i=1;i<=top;++i) {
		now=++tot;
		for(j=fir[st[i]];j;j=nex[j]) if(!vis[to[j]]) {
			if(d[to[j]]>1) return puts("-1"),0;
			s1[++tl]=++tot;
		}
		s1[++tl]=now;
	}
	tot=tl=0;
	for(i=top;i;--i) {
		now=++tot;
		for(j=fir[st[i]];j;j=nex[j])
			if(!vis[to[j]]) s2[++tl]=++tot; 
		s2[++tl]=now;
	}
	for(i=1;i<=tl;++i)
		if(s1[i]!=s2[i]) {
			cmp=s1[i]<s2[i];
			break;
		}
	if(cmp) for(i=1;i<=n;++i) printf("%d ",s1[i]);
	else for(i=1;i<=n;++i) printf("%d ",s2[i]);
}

Submission Info

Submission Time
Task F - Permutation Tree
User luogu_bot2
Language C++ (GCC 9.2.1)
Score 900
Code Size 1347 Byte
Status AC
Exec Time 44 ms
Memory 11852 KB

Compile Error

./Main.cpp: In function ‘int R()’:
./Main.cpp:9:10: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
    9 |  reg int x=0; reg bool f=0; reg char ch=getchar();
      |          ^
./Main.cpp:9:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
    9 |  reg int x=0; reg bool f=0; reg char ch=getchar();
      |                        ^
./Main.cpp:9:38: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
    9 |  reg int x=0; reg bool f=0; reg char ch=getchar();
      |                                      ^~
./Main.cpp: At global scope:
./Main.cpp:14:18: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   14 | void add(reg int u,reg int v)
      |                  ^
./Main.cpp:14:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   14 | void add(reg int u,reg int v)
      |                            ^
./Main.cpp:18:18: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   18 | void dfs(reg int u,reg int dis)
      |                  ^
./Main.cpp:18:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   18 | void dfs(reg int u,reg int dis)
      |                            ^~~
./Main.cpp: In function ‘void dfs(int, int)’:
./Main.cpp:21:14: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   21 |  for(reg int i=fir[u];i;i=nex[i])
      |              ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:26:10: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   26 |  reg int n=R(),i,j,u,v,now,cmp=0;
      |          ^
./Main.cpp:26:16: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   26 |  reg int n=R(),i,j,u,v,now,cmp=0;
      |                ^
./Main.cpp:26:18: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wr...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 55
Set Name Test Cases
Sample sample1.txt, sampleId.txt, sampleNo.txt
All id.txt, oshii_0.txt, oshii_1.txt, rnd10000_9876.txt, rnd10_4.txt, rnd10_l.txt, rnd20000_9876.txt, rnd20_18.txt, rnd20_4.txt, rnd20_l.txt, rnd3000_2984.txt, rnd3000_l.txt, rnd_0.txt, rnd_1.txt, rnd_10.txt, rnd_100.txt, rnd_1000.txt, rnd_10000.txt, rnd_100000.txt, rnd_1000000.txt, rnd_1000001.txt, rnd_1000002.txt, rnd_100001.txt, rnd_100002.txt, rnd_10001.txt, rnd_10002.txt, rnd_1001.txt, rnd_1002.txt, rnd_101.txt, rnd_102.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, rnd_5.txt, rnd_6.txt, rnd_7.txt, rnd_70.txt, rnd_700.txt, rnd_7000.txt, rnd_70000.txt, rnd_700000.txt, rnd_700001.txt, rnd_700002.txt, rnd_70001.txt, rnd_70002.txt, rnd_7001.txt, rnd_7002.txt, rnd_701.txt, rnd_702.txt, rnd_71.txt, rnd_72.txt, sample1.txt, sampleId.txt, sampleNo.txt, star.txt
Case Name Status Exec Time Memory
id.txt AC 44 ms 11852 KB
oshii_0.txt AC 23 ms 4344 KB
oshii_1.txt AC 17 ms 4192 KB
rnd10000_9876.txt AC 6 ms 2540 KB
rnd10_4.txt AC 1 ms 1576 KB
rnd10_l.txt AC 1 ms 1572 KB
rnd20000_9876.txt AC 9 ms 2916 KB
rnd20_18.txt AC 2 ms 1536 KB
rnd20_4.txt AC 1 ms 1552 KB
rnd20_l.txt AC 1 ms 1552 KB
rnd3000_2984.txt AC 3 ms 1836 KB
rnd3000_l.txt AC 2 ms 1720 KB
rnd_0.txt AC 19 ms 3948 KB
rnd_1.txt AC 16 ms 3776 KB
rnd_10.txt AC 2 ms 1540 KB
rnd_100.txt AC 1 ms 1556 KB
rnd_1000.txt AC 1 ms 1664 KB
rnd_10000.txt AC 3 ms 1908 KB
rnd_100000.txt AC 29 ms 5052 KB
rnd_1000000.txt AC 37 ms 7688 KB
rnd_1000001.txt AC 37 ms 8408 KB
rnd_1000002.txt AC 39 ms 10796 KB
rnd_100001.txt AC 9 ms 2324 KB
rnd_100002.txt AC 5 ms 2208 KB
rnd_10001.txt AC 1 ms 1608 KB
rnd_10002.txt AC 1 ms 1640 KB
rnd_1001.txt AC 1 ms 1556 KB
rnd_1002.txt AC 1 ms 1536 KB
rnd_101.txt AC 1 ms 1628 KB
rnd_102.txt AC 1 ms 1556 KB
rnd_2.txt AC 26 ms 4312 KB
rnd_3.txt AC 18 ms 4080 KB
rnd_4.txt AC 16 ms 4068 KB
rnd_5.txt AC 16 ms 3884 KB
rnd_6.txt AC 14 ms 3540 KB
rnd_7.txt AC 14 ms 3756 KB
rnd_70.txt AC 1 ms 1628 KB
rnd_700.txt AC 1 ms 1544 KB
rnd_7000.txt AC 3 ms 1780 KB
rnd_70000.txt AC 20 ms 4144 KB
rnd_700000.txt AC 29 ms 7164 KB
rnd_700001.txt AC 28 ms 5264 KB
rnd_700002.txt AC 27 ms 8280 KB
rnd_70001.txt AC 3 ms 1908 KB
rnd_70002.txt AC 3 ms 2096 KB
rnd_7001.txt AC 1 ms 1628 KB
rnd_7002.txt AC 2 ms 1576 KB
rnd_701.txt AC 1 ms 1544 KB
rnd_702.txt AC 1 ms 1580 KB
rnd_71.txt AC 1 ms 1584 KB
rnd_72.txt AC 1 ms 1588 KB
sample1.txt AC 2 ms 1540 KB
sampleId.txt AC 1 ms 1556 KB
sampleNo.txt AC 1 ms 1504 KB
star.txt AC 28 ms 5120 KB