QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#669820 | #8760. 不等式 | MIS_T__ | WA | 0ms | 3596kb | C++23 | 1.4kb | 2024-10-23 19:46:23 | 2024-10-23 19:46:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n,m;
cin >> n >> m;
vector g(n,vector<int>(0));
vector<int>num(n);
for ( int i = 0 ; i < m ; i++ ) {
int x,y,z;
cin >> x >> y >> z;
x--,y--,z--;
g[x].emplace_back(y);
g[x].emplace_back(z);
num[y]++;
num[z]++;
}
i64 ans = 0;
vector<i64>vis(n);
vector<i64>vis0(n);
int f = 0;
int cur;
auto dfs = [&](auto& dfs, int p)->void{
i64 res = 0;
vis0[p] = cur;
for ( auto q : g[p] ) {
if ( vis0[q] == cur ) f = 1;
if(!vis[q]) {
dfs(dfs,q);
}
res += vis[q];
}
if ( vis[p] > 1000000000 ) f = 1;
vis[p] = max(res,1LL);
};
for ( int i = 0 ; i < n ; i++ ) {
if ( num[i] == 0 ) {
cur = i+1;
dfs(dfs,i);
}
}
for ( int i = 0 ; i < n ; i++ ) {
if ( !vis[i] ) f = 1;
ans += vis[i];
}
if ( f ) {
cout << -1 << '\n';
return;
}
if ( ans > 1000000000 ) cout << -1 << '\n';
else cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while ( T-- ) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3596kb
input:
3 1 1 2 2
output:
-1
result:
wrong answer 1st numbers differ - expected: '4', found: '-1'