QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#542421 | #7860. Graph of Maximum Degree 3 | Repeater | ML | 177ms | 18096kb | C++20 | 2.4kb | 2024-09-01 01:25:50 | 2024-09-01 01:25:50 |
Judging History
answer
#include <bits/stdc++.h>
struct DSU
{
std::vector<int> f, siz;
DSU() {}
DSU(int n)
{
init(n);
}
void init(int n)
{
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x)
{
while (x != f[x])
{
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y)
{
return find(x) == find(y);
}
bool merge(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x)
{
return siz[find(x)];
}
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m; std::cin >> n >> m;
DSU dsu(n);
std::vector<std::vector<int>> adj(n);
std::map<std::pair<int, int>, int> vis;
for(int i = 0; i < m; i++)
{
int u, v, w; std::cin >> u >> v >> w;
u--, v--;
if(w == 0)
{
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
else
{
vis[{u, v}] = 1;
vis[{v, u}] = 1;
}
}
std::vector<int> fa(n, -1);
auto init = [&](auto init, int x, int lst) -> void
{
fa[x] = lst;
for(auto y : adj[x])
{
if(y == lst) continue;
init(init, y, x);
}
};
for(int i = 0; i < n; i++)
{
if(fa[i] != -1) continue;
init(init, i, -1);
}
std::vector<int> tmp;
auto check = [&]() -> int
{
int ok = 1;
for(int i = 0; i < tmp.size(); i++)
for(int j = i + 1; j < tmp.size(); j++)
if(vis.contains({tmp[i], tmp[j]}) || vis.contains({tmp[j], tmp[i]}))
dsu.merge(tmp[i], tmp[j]);
for(int i = 1; i < tmp.size(); i++)
if(!dsu.same(tmp[0], tmp[i])) ok = 0;
for(auto i : tmp) dsu.f[i] = i;
// std::cerr << ok << " : ";
// for(auto i : tmp) std::cerr << i + 1 << " ";
// std::cerr << "\n";
return ok;
};
int ans = 0;
auto cacl = [&](auto cacl, int x) -> void
{
if(tmp.size() > 4) return;
ans += check();
for(auto y : adj[x])
{
if(y == fa[x]) continue;
tmp.emplace_back(y);
cacl(cacl, y);
}
};
for(int i = 0; i < n; i++)
{
tmp.clear();
tmp.emplace_back(i);
cacl(cacl, i);
}
std::cout << ans << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
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: 3788kb
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: 3788kb
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: 3848kb
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: 0
Accepted
time: 111ms
memory: 18096kb
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:
144604
result:
ok 1 number(s): "144604"
Test #6:
score: 0
Accepted
time: 114ms
memory: 18096kb
input:
100000 133388 86620 74346 0 74346 19047 0 54911 19047 0 86620 19047 1 86620 54911 1 74346 54911 1 23715 93094 0 93094 91208 0 63189 91208 0 23715 91208 1 23715 63189 1 93094 63189 1 99337 41426 1 99337 41426 0 83742 45546 0 45546 73862 0 83742 45546 1 83742 73862 1 85256 2812 0 2812 59368 0 85918 59...
output:
144348
result:
ok 1 number(s): "144348"
Test #7:
score: 0
Accepted
time: 177ms
memory: 18096kb
input:
100000 150000 86541 24385 0 24385 75745 0 52353 75745 0 86541 75745 1 86541 52353 1 24385 52353 1 89075 78015 0 89075 78015 1 52519 74846 0 74846 12045 0 73265 12045 0 52519 12045 1 52519 73265 1 74846 73265 1 17884 63159 0 63159 47308 0 56073 47308 0 17884 47308 1 17884 56073 1 63159 56073 1 72134 ...
output:
144639
result:
ok 1 number(s): "144639"
Test #8:
score: 0
Accepted
time: 163ms
memory: 18048kb
input:
100000 150000 91951 68612 1 91951 68612 0 18361 92673 0 92673 52678 0 86520 52678 0 18361 52678 1 18361 86520 1 92673 86520 1 58779 2421 0 58779 2421 1 66622 6461 0 6461 96943 0 66622 6461 1 66622 96943 1 27201 480 1 27201 480 0 19082 3895 0 3895 17796 0 3117 17796 0 19082 17796 1 19082 3117 1 3895 ...
output:
144471
result:
ok 1 number(s): "144471"
Test #9:
score: 0
Accepted
time: 172ms
memory: 18096kb
input:
100000 150000 43756 3552 0 3552 90269 0 43756 3552 1 43756 90269 1 11104 36935 1 11104 36935 0 11648 5480 0 5480 45320 0 11648 5480 1 11648 45320 1 19216 85746 0 19216 85746 1 68825 11173 0 11173 43155 0 68825 11173 1 68825 43155 1 27349 75259 0 27349 75259 1 1704 24478 0 24478 5980 0 1704 24478 1 1...
output:
144217
result:
ok 1 number(s): "144217"
Test #10:
score: 0
Accepted
time: 166ms
memory: 18048kb
input:
99999 149998 51151 43399 0 51151 43399 1 45978 28343 0 28343 9008 0 85724 9008 0 45978 9008 1 45978 85724 1 28343 85724 1 79446 12915 0 12915 65925 0 28869 65925 0 79446 65925 1 79446 28869 1 12915 28869 1 82642 95556 0 95556 68817 0 68334 68817 0 82642 68817 1 82642 68334 1 95556 68334 1 61212 7638...
output:
144219
result:
ok 1 number(s): "144219"
Test #11:
score: -100
Memory Limit Exceeded
input:
100000 149999 26736 28785 0 28785 37945 0 26736 28785 1 26736 37945 1 1240 74368 0 74368 45022 0 1240 74368 1 1240 45022 1 40673 1276 0 1276 56395 0 40673 1276 1 40673 56395 1 35181 63341 0 63341 35131 0 60120 35131 0 35181 35131 1 35181 60120 1 63341 60120 1 99363 36973 0 99363 36973 1 85717 77683 ...