QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#297403#7860. Graph of Maximum Degree 3ucup-team1525#WA 42ms15192kbC++201.9kb2024-01-04 13:22:432024-01-04 13:22:43

Judging History

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

  • [2024-01-04 13:22:43]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:15192kb
  • [2024-01-04 13:22:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
vector<int> e[2][N];
vector<int> v;
int ans;
int fa[N];
int getfa(int x)
{
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y)
{
    x=getfa(x);
    y=getfa(y);
    if (x!=y)
        fa[x]=y;
}
void check()
{
    for (int i=0;i<v.size();++i)    
        for (int j=i+1;j<v.size();++j)
            if (v[i]==v[j])
                return;
    for (int x:v)
        fa[x]=x;
    for (int x:v)
        for (int y:e[1][x])
            if (fa[y]!=0)
                merge(x,y);
    set<int> s;
    for (int x:v)
    {
        fa[x]=getfa(x);
        s.insert(fa[x]);
    }
    if (s.size()==1)
        ++ans;
    for (int x:v)
        fa[x]=0;
}
inline void work(int x)
{
    if (e[0][x].size()==3||e[0][x].size()==0)
        return;
    v.clear();
    v.push_back(x);
    for (int y:e[0][x])
        if (y>x)
        {
            v.push_back(y);
            check();
            v.pop_back();
        }
    if (e[0][x].size()==2)
    {
        v.push_back(e[0][x][0]);
        v.push_back(e[0][x][1]);
        bool b=true;
        for (int y:e[0][e[0][x][0]])
            if (y==e[0][x][1])
                b=false;
        if (b||(x<e[0][x][0]&&x<e[0][x][1]))
            check();
        for (int i=0;i<=1;++i)
            if (e[0][x][i]>x&&(int)e[0][e[0][x][i]].size()==2)
            {
                int z=x;
                for (int o:e[0][e[0][x][i]])
                    z^=o;
                v.push_back(z);
                check();
                v.pop_back();
            }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0,u,v,w;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        e[w][u].push_back(v);
        e[w][v].push_back(u);
    }
    ans=n;
    for (int i=1;i<=n;++i)
        work(i);
    cout<<ans<<endl;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 8484kb

input:

3 4
1 2 0
1 3 1
2 3 0
2 3 1

output:

5

result:

ok 1 number(s): "5"

Test #2:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

20 28
9 6 1
9 6 0
3 8 0
8 4 0
3 8 1
3 4 1
2 13 0
13 1 0
19 1 0
2 1 1
2 19 1
13 19 1
14 15 1
14 15 0
7 12 0
12 17 0
20 17 0
7 17 1
7 20 1
12 20 1
16 18 0
18 10 0
5 10 0
16 10 1
16 5 1
18 5 1
4 6 0
9 11 0

output:

27

result:

ok 1 number(s): "27"

Test #4:

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

input:

100 150
93 23 0
23 81 0
76 81 0
93 81 1
93 76 1
23 76 1
100 65 0
65 56 0
19 56 0
100 56 1
100 19 1
65 19 1
2 98 0
2 98 1
26 63 0
63 90 0
26 63 1
26 90 1
6 11 0
11 67 0
6 11 1
6 67 1
37 89 0
89 64 0
25 64 0
37 64 1
37 25 1
89 25 1
84 10 0
10 29 0
75 29 0
84 29 1
84 75 1
10 75 1
7 70 1
7 70 0
28 92 0
...

output:

141

result:

ok 1 number(s): "141"

Test #5:

score: -100
Wrong Answer
time: 42ms
memory: 15192kb

input:

100000 133680
36843 86625 0
86625 63051 0
35524 63051 0
36843 63051 1
36843 35524 1
86625 35524 1
55797 82715 0
55797 82715 1
70147 35104 0
35104 91732 0
70147 35104 1
70147 91732 1
94917 70395 0
70395 68250 0
24100 68250 0
94917 68250 1
94917 24100 1
70395 24100 1
83033 18450 1
83033 18450 0
34462 ...

output:

144602

result:

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