QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#101965#6354. 4zhouhuanyiWA 1ms9896kbC++111.4kb2023-05-01 22:30:542023-05-01 22:30:56

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-01 22:30:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9896kb
  • [2023-05-01 22:30:54]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<bitset>
#include<vector>
#define N 100000
#define M 512
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;
}
struct reads
{
    int num,data;
};
int n,m,X[N+1],Y[N+1],num[N+1],deg[N+1];
long long ans;
vector<reads>E[N+1];
vector<int>p[N+1];
bitset<M+1>B[N+1];
void add(int x,int y,int z)
{
    E[x].push_back((reads){y,z});
    return;
}
int main()
{
    n=read(),m=read();
    for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),deg[X[i]]++,deg[Y[i]]++;
    for (int i=1;i<=m;++i)
    {
	if (deg[X[i]]<deg[Y[i]]) add(X[i],Y[i],i);
	else add(Y[i],X[i],i);
    }
    for (int i=1;i<=n;++i)
    {
	for (int j=0;j<E[i].size();++j) num[E[i][j].num]=E[i][j].data;
	for (int j=0;j<E[i].size();++j)
	    for (int k=0;k<E[E[i][j].num].size();++k)
		if (i!=E[E[i][j].num][k].num&&num[E[E[i][j].num][k].num])
		{
                    p[E[i][j].data].push_back(E[E[i][j].num][k].num);
		    p[E[E[i][j].num][k].data].push_back(i);
		    p[num[E[E[i][j].num][k].num]].push_back(E[i][j].num);
		}
    }
    for (int i=1;i<=m;i+=M)
    {
	for (int j=1;j<=n;++j) B[j].reset();
	for (int j=i;j<=min(i+M-1,m);++j)
	    for (int k=0;k<p[j].size();++k)
		B[p[j][k]][j-i]=1;
	for (int j=1;j<=m;++j) ans+=(B[X[j]]&B[Y[j]]).count();
    }
    printf("%lld\n",ans/6);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9732kb

input:

5 9
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 9896kb

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 9752kb

input:

50 50
28 35
12 24
31 50
10 24
21 44
5 31
23 36
31 45
6 39
4 8
13 37
42 48
17 45
19 33
12 21
19 32
16 43
12 47
25 31
40 48
8 49
43 48
6 42
27 34
13 39
17 40
13 35
3 49
20 24
5 12
43 44
15 37
24 27
8 43
4 22
17 38
28 47
29 46
3 15
9 49
1 41
43 45
3 6
37 48
13 30
11 43
8 25
33 38
16 32
32 41

output:

1

result:

wrong answer 1st numbers differ - expected: '0', found: '1'