QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#678089 | #8760. 不等式 | QSteve_Paul | ML | 0ms | 3812kb | C++23 | 1.3kb | 2024-10-26 14:01:03 | 2024-10-26 14:01:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve()
{
int n, m;
cin >> n >> m;
vector<set<int>> v(n + 1);
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 1; i <= n; i++)
{
int x, y, z;
cin >> x >> y >> z;
if (v[y].count(x) || v[z].count(x))
{
cout << -1 << "\n";
return;
}
v[x].insert(y);
v[x].insert(z);
g[x].emplace_back(y, z);
}
vector<i64> ans(n + 1);
function<void(int)> dfs = [&](int x) {
if (ans[x])
return;
i64 mx = 1;
for (auto [y, z] : g[x])
{
dfs(y);
dfs(z);
mx = max(mx, ans[y] + ans[z]);
}
ans[x] = mx;
};
for (int i = 1; i <= n; i++)
dfs(i);
i64 res = accumulate(ans.begin() + 1, ans.begin() + n + 1, 0LL);
if (res > 1e9)
{
cout << -1 << "\n";
return;
}
cout << res << "\n";
}
int main()
{
#ifdef lijn
freopen("/home/lijn/acm_practice/.build/input.in", "r", stdin);
freopen("/home/lijn/acm_practice/.build/output.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3728kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 2 1 2 3 2 3 4
output:
8
result:
ok 1 number(s): "8"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
10 2 1 2 3 2 3 4
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
10 2 1 2 2 2 3 4
output:
14
result:
ok 1 number(s): "14"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 3 1 2 3 1 8 8 2 3 3
output:
13
result:
ok 1 number(s): "13"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
20 2 1 2 3 2 3 3
output:
23
result:
ok 1 number(s): "23"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
20 3 7 14 6 1 2 3 4 7 20
output:
24
result:
ok 1 number(s): "24"
Test #19:
score: -100
Memory Limit Exceeded
input:
20 4 1 2 2 6 10 6 2 3 3 3 4 5