QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #645701 | #7860. Graph of Maximum Degree 3 | CanShangya | WA | 0ms | 3812kb | C++14 | 2.8kb | 2024-10-16 19:32:13 | 2024-10-16 19:32:14 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
struct DSU{
vector<int>fa;
DSU(int n)
{
for(int i = 0; i <= n; i++)
fa.push_back(i);
}
int found(int x)
{
return fa[x] == x ? x : (fa[x] = found(fa[x]));
}
void merge(int x, int y)
{
x = found(x), y = found(y);
if(x < y){swap(x, y);};
if(x != y)
{
fa[x] = y;
}
}
};
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<int> >g1(n+10);
vector<vector<int> >g2(n+10);
DSU dsu1(n+1);
DSU dsu2(n+1);
for(int i = 0; i < m; i++)
{
int a, b, col;
cin >> a >> b >> col;
if(col == 0)
{
g1[a].push_back(b);
g1[b].push_back(a);
dsu1.merge(a,b);
}
else
{
g2[a].push_back(b);
g2[b].push_back(a);
dsu2.merge(a,b);
}
}
vector<int>vis(n+10);
vector<int>pend;
int ans = 0;
map<vector<int>, int>mp;
auto dfs = [&](auto &&dfs, int now)
{
int cnt = pend.size();
if(cnt > 4)
{
return;
}
// for(int i = 0; i < cnt; i++)
// {
// cout << pend[i] << ' ';
// }cout << '\n';
bool op = true;
int num = 0;
if(cnt != 1)
{
vector<int> x(cnt+10);
for(int i = 0; i < cnt; i ++)
{
for(int k = i+1; k < cnt; k++)
{
for(auto j : g2[pend[i]])
{
if(j == pend[k])
{
x[i] = 1;
x[k] = 1;
break;
}
}
}
}
for(int i = 0; i < cnt; i++)
{
if(!x[i])
op = false;
}
}
if(op)
{
ans++;
}
for(auto i : g1[now])
{
if(!vis[i])
{
vis[i] = 1;
pend.push_back(i);
dfs(dfs, i);
vis[i] = 0;
}
}
while(pend.size() > 4)
{
pend.pop_back();
}
};
for(int i = 1; i <= n; i++)
{
vis[i] = 1;
pend.push_back(i);
dfs(dfs, i);
pend.clear();
// pend.pop_back();
}
cout << ans << '\n';
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
// int _;
// cin >> _;
// while(_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
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: 0ms
memory: 3484kb
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: 0ms
memory: 3540kb
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: -100
Wrong Answer
time: 0ms
memory: 3812kb
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:
145
result:
wrong answer 1st numbers differ - expected: '141', found: '145'