QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#297403 | #7860. Graph of Maximum Degree 3 | ucup-team1525# | WA | 42ms | 15192kb | C++20 | 1.9kb | 2024-01-04 13:22:43 | 2024-01-04 13:22:43 |
Judging History
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'