QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115155#5413. 同构判定鸡zhouhuanyi97.015306 22ms12052kbC++113.3kb2023-06-24 18:13:332023-06-24 18:13:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-24 18:13:34]
  • 评测
  • 测评结果：97.015306
  • 用时：22ms
  • 内存：12052kb
查看
  • [2023-06-24 18:13:33]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 3000
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int gcd(int x,int y)
{
    if (!y) return x;
    return gcd(y,x%y);
}
int T,p,n,m,sn,sm,type;
bool E[N+1][N+1],used[N+1];
void adder(int x,int y)
{
    E[x][y]=E[y][x]=1;
    return;
}
int F(int x,int y)
{
    return x*p+y+1;
}
int G(int x,int y,int z)
{
    return x*p*p+y*p+z+1;
}
int main()
{
    int x,y,d1,d2,d3,cnt,rst;
    bool op;
    T=read(),type=read();
    while (T--)
    {
	n=read(),m=read();
	for (int i=1;i<=m;++i) x=read(),y=read();
	sn=read(),sm=read();
	if (type<=2)
	{
	    cnt=0;
	    for (int i=1;i<=sn;++i)
		for (int j=i+1;j<=sn;++j)
		    if ((j-i)%(n-1)!=0)
			cnt++;
	    printf("%d %d\n",sn,cnt);
	    for (int i=1;i<=sn;++i)
		for (int j=i+1;j<=sn;++j)
		    if ((j-i)%(n-1)!=0)
			printf("%d %d\n",i,j);
	}
	else if (type==3)
	{
	    rst=sn/25;
	    for (int i=0;i<5;++i)
		for (int j=0;j<5;++j)
		    adder(i*5+j+1,i*5+(j+1)%5+1);
	    for (int i=0;i<5;++i) adder(i*5+1,((i+1)%5)*5+1),adder(i*5+2,((i+1)%5)*5+3),adder(i*5+3,((i+1)%5)*5+5),adder(i*5+4,((i+1)%5)*5+2),adder(i*5+5,((i+1)%5)*5+4);
	    printf("%d %d\n",sn,sm);
	    for (int i=1;i<=rst;++i)
		for (int j=1;j<=25;++j)
		    for (int k=j+1;k<=25;++k)
			if (E[j][k])
			    printf("%d %d\n",(i-1)*25+j,(i-1)*25+k);
	    for (int i=1;i<=sn%25;++i) printf("%d %d\n",i,rst*25+i),printf("%d %d\n",25+i,rst*25+i);
	}
	else if (type==4)
	{
	    cnt=p=0;
	    while ((p+1)*(p+1)<=sn) p++;
	    for (int i=1;i<=sn;++i)
		for (int j=1;j<=sn;++j)
		    E[i][j]=0;
	    for (int i=0;i<p;++i)
		for (int j=0;j<p;++j)
		    for (int k=0;k<p;++k)
			adder(F(i,j),F(k,(i*k+p-j)%p));
	    for (int i=1;i<=sn;++i)
		for (int j=i+1;j<=sn;++j)
		    if (E[i][j])
			cnt++;
	    printf("%d %d\n",sn,cnt);
	    for (int i=1;i<=sn;++i)
		for (int j=i+1;j<=sn;++j)
		    if (E[i][j])
			printf("%d %d\n",i,j);
	}
	else if (type==5)
	{
	    sn=2809,cnt=p=0;
	    while ((p+1)*(p+1)<=sn) p++;
	    for (int i=0;i<p;++i)
		for (int j=0;j<p;++j)
		    for (int k=0;k<p;++k)
			adder(F(i,j),F(k,(i*k+p-j)%p));
	    for (int i=1;i<=sn;++i)
		for (int j=i+1;j<=sn;++j)
		    if (E[i][j])
			cnt++;
	    printf("%d %d\n",sn,cnt);
	    for (int i=1;i<=sn;++i)
		for (int j=i+1;j<=sn;++j)
		    if (E[i][j])
			printf("%d %d\n",i,j);
	}
	else
	{
	    cnt=p=0;
	    while ((p+1)*(p+1)*(p+1)<=sn) p++;
	    used[0]=1;
	    for (int i=0;i<p;++i)
		for (int j=0;j<p;++j)
		    for (int k=0;k<p;++k)
			for (int i2=0;i2<p;++i2)
			    for (int j2=0;j2<p;++j2)
				for (int k2=0;k2<p;++k2)
				{
				    d1=abs(i-i2),d2=abs(j-j2),d3=abs(k-k2),op=0;
				    if (d1*d1+d2*d2+d3*d3==14) op=1;
				    if (d1&&(p-d1)*(p-d1)+d2*d2+d3*d3==14) op=1;
				    if (d2&&d1*d1+(p-d2)*(p-d2)+d3*d3==14) op=1;
				    if (d1&&d2&&(p-d1)*(p-d1)+(p-d2)*(p-d2)+d3*d3==14) op=1;
				    if (op) E[G(i,j,k)][G(i2,j2,k2)]=1;
				}
	    for (int i=1;i<=sn;++i)
		for (int j=i+1;j<=sn;++j)
		    if (E[i][j])
			cnt++;
	    printf("%d %d\n",sn,cnt);
	    for (int i=1;i<=sn;++i)
		for (int j=i+1;j<=sn;++j)
		    if (E[i][j])
			printf("%d %d\n",i,j);
	}
    }
    return 0;
}
源文件, 语言: C++11

详细

Test #1:

score: 5
Accepted
time: 0ms
memory: 3624kb

input:

10 1
3 3
1 2
1 3
2 3
33 272
3 3
1 2
1 3
2 3
28 196
3 3
1 2
1 3
2 3
92 2116
3 3
1 2
1 3
2 3
29 210
3 3
1 2
1 3
2 3
62 961
3 3
1 2
1 3
2 3
97 2352
3 3
1 2
1 3
2 3
60 900
3 3
1 2
1 3
2 3
70 1225
3 3
1 2
1 3
2 3
67 1122
3 3
1 2
1 3
2 3
67 1122

output:

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

result:

ok correct! (10 test cases)

Test #2:

score: 10
Accepted
time: 2ms
memory: 3752kb

input:

10 2
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
28 293
8 28
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
8 26
4 6
1 2
1 3
1 4
2 3
2 4
3 4
82 2240
3 3
1 2
1 3
2 3
46 528
4 6
1 2
1 3
1 4
2 3
2 4
3 4
42 587
9 36
1 2
1 3
1 4
1 5
1 6
1 ...

output:

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

result:

ok correct! (10 test cases)

Test #3:

score: 10
Accepted
time: 4ms
memory: 3656kb

input:

10 3
4 4
1 2
2 3
3 4
4 1
387 774
4 4
1 2
2 3
3 4
4 1
668 1336
4 4
1 2
2 3
3 4
4 1
1403 2806
4 4
1 2
2 3
3 4
4 1
1516 3032
4 4
1 2
2 3
3 4
4 1
1601 3202
4 4
1 2
2 3
3 4
4 1
1649 3298
4 4
1 2
2 3
3 4
4 1
1722 3444
4 4
1 2
2 3
3 4
4 1
1854 3708
4 4
1 2
2 3
3 4
4 1
1926 3852
4 4
1 2
2 3
3 4
4 1
1989 3978

output:

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

result:

ok correct! (10 test cases)

Test #4:

score: 15
Accepted
time: 22ms
memory: 10824kb

input:

10 4
4 4
1 2
2 3
3 4
4 1
169 1014
4 4
1 2
2 3
3 4
4 1
529 5819
4 4
1 2
2 3
3 4
4 1
841 11774
4 4
1 2
2 3
3 4
4 1
961 14415
4 4
1 2
2 3
3 4
4 1
1369 24642
4 4
1 2
2 3
3 4
4 1
1681 33620
4 4
1 2
2 3
3 4
4 1
1849 38829
4 4
1 2
2 3
3 4
4 1
361 3249
4 4
1 2
2 3
3 4
4 1
289 2312
4 4
1 2
2 3
3 4
4 1
9 9

output:

169 1092
1 14
1 27
1 40
1 53
1 66
1 79
1 92
1 105
1 118
1 131
1 144
1 157
2 13
2 26
2 39
2 52
2 65
2 78
2 91
2 104
2 117
2 130
2 143
2 156
2 169
3 12
3 25
3 38
3 51
3 64
3 77
3 90
3 103
3 116
3 129
3 142
3 155
3 168
4 11
4 24
4 37
4 50
4 63
4 76
4 89
4 102
4 115
4 128
4 141
4 154
4 167
5 10
5 23
5 3...

result:

ok correct! (10 test cases)

Test #5:

score: 30
Accepted
time: 11ms
memory: 12052kb

input:

1 5
4 4
1 2
2 3
3 4
4 1
2850 24300

output:

2809 74412
1 54
1 107
1 160
1 213
1 266
1 319
1 372
1 425
1 478
1 531
1 584
1 637
1 690
1 743
1 796
1 849
1 902
1 955
1 1008
1 1061
1 1114
1 1167
1 1220
1 1273
1 1326
1 1379
1 1432
1 1485
1 1538
1 1591
1 1644
1 1697
1 1750
1 1803
1 1856
1 1909
1 1962
1 2015
1 2068
1 2121
1 2174
1 2227
1 2280
1 2333
...

result:

points 1.0 m' = 74412, 3M = 72900, points = 30.304790

Test #6:

score: 27.0153
Acceptable Answer
time: 0ms
memory: 4600kb

input:

1 6
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
343 2350

output:

343 5880
1 67
1 73
1 80
1 88
1 109
1 121
1 128
1 144
1 157
1 163
1 184
1 192
1 206
1 212
1 233
1 241
1 256
1 268
1 275
1 291
1 312
1 318
1 325
1 333
2 68
2 74
2 81
2 89
2 110
2 120
2 122
2 127
2 129
2 145
2 158
2 162
2 164
2 183
2 185
2 193
2 207
2 211
2 213
2 232
2 234
2 242
2 257
2 267
2 269
2 274...

result:

points 0.90051020410 m' = 5880, 3M = 7050, points = 27.015306
English 繁體中文 简体中文

服务器时间: 2024-11-30 14:30:44 | 开源项目