QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#395876#6441. Ancient Magic Circle in Teyvatfeather_lifeWA 5ms26236kbC++143.8kb2024-04-21 23:36:392024-04-21 23:36:39

Judging History

This is the latest submission verdict.

  • [2024-04-21 23:36:39]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 26236kb
  • [2024-04-21 23:36:39]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
int n,m;
struct edge
{
    int v,x;
};
struct edge2
{
    int x,y;
}ed[maxn << 1];
int in[maxn];
vector<edge> g[maxn],big[maxn],small[maxn];//大点,小点,定义参上
int ans[10];
int mark[maxn],id[maxn];
int deg[maxn];
int vis[maxn];
int a[maxn];
int cnt;
int c[10] = {1,-1,1,1,-1,-1,-1,1,1,-1};
signed main()
{
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        int u,v;
        cin >> u >> v;
        ed[i] = {u,v};
        g[u].push_back({v,i});
        g[v].push_back({u,i});
        in[u]++;
        in[v]++;
    }
    ans[0] = (__int128)n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4;//全部状况
    for(int i = 1;i <= n;i++)
    {
        for(int j = 0;j < g[i].size();j++)
        {
            if(in[i] > in[g[i][j].v] || (in[i] == in[g[i][j].v] && i > g[i][j].v))
            {
                big[i].push_back(g[i][j]);
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 0;j < g[i].size();j++)
        {
            if(in[i] < in[g[i][j].v] || (in[i] == in[g[i][j].v] && i < g[i][j].v))
            {
                small[i].push_back(g[i][j]);
            }
        }
    }
    ans[1] = m * (n - 2) * (n - 3) / 2;
    for(int i = 1;i <= m;i++)
    {
        ans[2] += m - (in[ed[i].x] + in[ed[i].y] - 1);
    }
    ans[2] /= 2;
    for(int i = 1;i <= n;i++)
    {
        ans[3] += in[i] * (in[i] - 1) / 2 * (n - 3);
    }
    int cur = 0;
    for(int i = 1;i <= m;i++)
    {
        int x = ed[i].x,y = ed[i].y;
        ans[4] += (in[x] - 1) * (in[y] - 1);
    }
    for(int i = 1;i <= n;i++)
    {
        for(edge e : big[i])
        {
            mark[e.v] = 1;
            id[e.v] = e.x;
        }
        for(edge e : big[i])
        {
            for(edge v : big[e.v])
            {
                if(mark[v.v])
                {
                    cur++;
                    ans[7] += in[i] + in[e.v] + in[v.v] - 6;
                    deg[id[v.v]]++;
                    deg[e.x]++;
                    deg[v.x]++;
                }
            }
        }
        for(edge e : big[i])
        {
            mark[e.v] = 0;
        }
    }
    ans[4] -= cur * 3;
    ans[5] += cur * (n - 3);
    for(int i = 1;i <= n;i++)
    {
        ans[6] += in[i] * (in[i] - 1) / 2 * (in[i] - 2) / 3;
    }
    for(int i = 1;i <= m;i++)
    {
        ans[9] += deg[i] * (deg[i] - 1) / 2;
    }
    int del = 0;
    for(int i = 1;i <= n;i++)
    {
        int cnt = 0;
        for(edge e : big[i])
        {
            for(edge v : g[e.v])
            {
                if(v.v != i)
                {
                    if(!vis[v.v])
                    {
                        a[++cnt] = v.v;
                    }
                    vis[v.v]++;
                }
            }
        }
        for(int j = 1;j <= cnt;j++)
        {
            ans[8] += vis[a[j]] * (vis[a[j]] - 1) / 2;
            vis[a[j]] = 0;
        }
    }
    for(int i = 1;i <= n;i++)
    {
        int cnt = 0;
        for(edge e : big[i])
        {
            for(edge v : small[e.v])
            {
                if(v.v != i)
                {
                    if(!vis[v.v])
                    {
                        a[++cnt] = v.v;
                    }
                    vis[v.v]++;
                }
            }
        }
        for(int j = 1;j <= cnt;j++)
        {
            del += vis[a[j]] * (vis[a[j]] - 1) / 2;
            vis[a[j]] = 0;
        }
    }
    ans[8] -= del / 2;
    int res = 0;
    for(int i = 0;i <= 9;i++){res += c[i] * ans[i];if(n == 633 && m != 0)cout << ans[i] << "\n";};
    cout << abs(res);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 26212kb

input:

7 6
1 2
1 3
1 4
2 3
2 4
3 4

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 20000kb

input:

4 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 24068kb

input:

4 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 4ms
memory: 24188kb

input:

4 2
1 2
1 3

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 3ms
memory: 26204kb

input:

4 2
1 2
3 4

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 24056kb

input:

4 3
1 2
1 3
1 4

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 24188kb

input:

4 3
1 2
2 3
3 4

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 0ms
memory: 26236kb

input:

4 3
1 2
2 3
1 3

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 0ms
memory: 26200kb

input:

4 4
1 2
2 3
1 3
1 4

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 0ms
memory: 24060kb

input:

4 4
1 2
2 3
3 4
1 4

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 0ms
memory: 26228kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #12:

score: 0
Accepted
time: 3ms
memory: 24152kb

input:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 2ms
memory: 17948kb

input:

633 0

output:

6626427570

result:

ok 1 number(s): "6626427570"

Test #14:

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

input:

633 100
284 424
27 560
19 484
92 558
59 385
440 577
11 420
341 543
285 330
430 569
88 259
13 499
444 557
418 483
167 220
185 497
175 489
246 400
387 577
125 303
99 336
152 437
116 324
229 472
200 338
46 197
368 399
345 386
92 439
121 132
50 310
444 525
454 631
174 337
276 337
476 597
405 557
99 263
...

output:

6626427570
19876500
4917
20790
10
0
3
0
0
0
6606576764

result:

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