QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#669835 | #8760. 不等式 | zwu2021016689 | WA | 2ms | 12304kb | C++17 | 1.2kb | 2024-10-23 19:48:12 | 2024-10-23 19:48:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define dg(x) cout<<#x<<'='<<x<<'\n';
#define all(x) x.begin(),x.end()
const int N=2e5+10;
vector<int>g[N];
int vis[N],dis[N],in[N];
int co=0;
int ans=0;
int root;
set<int>s;
void dfs(int x){
//dg(x)
if(co==1) return ;
if(s.find(x)!=s.end()){
co=1;
return ;
}
s.insert(x);
if(vis[x]){
s.erase(s.find(x));
return ;
}
vis[x]=1;
for(auto u:g[x]){
dfs(u);
}
if(g[x].size()==0){
dis[x]=1;
}
else{
vector<int>v;
for(auto u:g[x]) v.push_back(dis[u]);
sort(all(v),greater<int>());
dis[x]+=v[0];
if(v.size()>=2) dis[x]+=v[1];
}
s.erase(s.find(x));
}
inline void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
g[x].push_back(y);
g[x].push_back(z);
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
dfs(i);
s.clear();
}
for(int i=1;i<=n;i++) ans+=dis[i];
if(co) ans=-1;
cout<<ans<<'\n';
}
/*
5 2
1 2 3
3 1 2
6 3
1 2 3
3 4 5
6 3 5
3 1
1 2 2
10 3
1 2 3
1 8 8
2 3 3
*/
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10840kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9408kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 9248kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 8916kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 1ms
memory: 8920kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 9372kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 1ms
memory: 9240kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 1ms
memory: 9632kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 2ms
memory: 9680kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 1ms
memory: 8960kb
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: 11920kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 2ms
memory: 12304kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 0ms
memory: 9984kb
input:
10 2 1 2 3 2 3 4
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 1ms
memory: 9228kb
input:
10 2 1 2 2 2 3 4
output:
14
result:
ok 1 number(s): "14"
Test #15:
score: 0
Accepted
time: 2ms
memory: 9600kb
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: 1ms
memory: 10716kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 0ms
memory: 8920kb
input:
20 2 1 2 3 2 3 3
output:
23
result:
ok 1 number(s): "23"
Test #18:
score: 0
Accepted
time: 1ms
memory: 12208kb
input:
20 3 7 14 6 1 2 3 4 7 20
output:
24
result:
ok 1 number(s): "24"
Test #19:
score: 0
Accepted
time: 1ms
memory: 9232kb
input:
20 4 1 2 2 6 10 6 2 3 3 3 4 5
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: 0
Accepted
time: 1ms
memory: 10632kb
input:
20 5 1 17 3 1 2 3 2 3 4 3 4 5 8 13 16
output:
28
result:
ok 1 number(s): "28"
Test #21:
score: 0
Accepted
time: 1ms
memory: 10736kb
input:
200 9 1 2 2 2 3 3 3 4 5 91 112 195 126 145 82 4 5 5 53 2 15 5 6 6 6 7 7
output:
318
result:
ok 1 number(s): "318"
Test #22:
score: 0
Accepted
time: 1ms
memory: 9156kb
input:
200 17 1 2 2 100 69 47 159 84 111 2 3 3 3 4 5 4 5 5 8 9 76 5 6 7 158 81 154 189 62 45 192 159 181 6 7 7 15 181 91 7 193 152 140 65 66 7 8 9 32 157 67
output:
428
result:
ok 1 number(s): "428"
Test #23:
score: 0
Accepted
time: 1ms
memory: 8932kb
input:
200 25 118 152 40 172 193 173 126 32 89 1 2 3 147 148 112 2 3 4 3 4 4 35 116 95 179 193 64 70 22 55 4 5 5 5 6 6 24 74 182 184 168 129 6 7 8 7 8 9 109 63 173 8 9 10 38 125 106 68 147 40 33 65 46 144 12 168 9 10 11 10 11 11 190 73 48
output:
835
result:
ok 1 number(s): "835"
Test #24:
score: 0
Accepted
time: 0ms
memory: 10488kb
input:
200 33 1 2 3 165 80 199 2 3 4 10 80 12 3 4 5 4 5 6 5 6 7 128 1 190 6 7 7 166 124 95 7 8 9 60 51 80 25 158 81 108 107 99 8 9 9 9 10 10 10 11 12 54 41 100 11 12 13 176 185 149 12 13 13 13 14 14 14 15 16 15 16 17 16 17 17 128 73 196 17 18 19 93 169 141 18 19 19 19 20 20 20 21 21 21 22 22 12 55 32
output:
543121
result:
ok 1 number(s): "543121"
Test #25:
score: 0
Accepted
time: 0ms
memory: 9532kb
input:
200 41 1 2 3 2 3 3 3 4 4 4 5 5 175 3 161 5 6 7 6 7 8 7 8 9 8 9 10 9 10 10 10 11 11 24 15 157 82 57 72 161 48 197 149 96 16 30 3 131 165 114 21 143 110 56 11 12 12 12 13 13 13 14 14 62 183 153 14 15 15 15 16 16 192 139 91 178 54 86 16 17 18 158 59 18 17 18 19 35 91 197 18 19 20 99 129 43 168 76 146 7...
output:
-1
result:
ok 1 number(s): "-1"
Test #26:
score: 0
Accepted
time: 1ms
memory: 12024kb
input:
2000 81 97 630 1373 398 361 536 1 2 3 2 3 4 3 4 5 1573 1392 1526 645 1562 79 1833 239 840 4 5 5 1122 972 412 5 6 7 1089 190 1311 672 1664 887 6 7 8 805 1221 1635 7 8 8 8 9 9 1001 1271 267 176 200 567 1800 762 1129 1978 1273 429 1965 155 68 295 1714 836 499 1093 465 9 10 11 10 11 11 11 12 13 12 13 14...
output:
1474361
result:
ok 1 number(s): "1474361"
Test #27:
score: 0
Accepted
time: 1ms
memory: 10604kb
input:
2000 161 594 271 957 633 1085 1384 1133 1233 916 1463 1353 621 1 2 2 514 1052 224 814 744 1837 44 195 1186 2 3 4 1272 606 1531 739 706 1827 1862 1014 834 3 4 5 4 5 5 1063 1246 1103 935 318 593 1657 93 324 583 987 1283 1258 1051 866 1187 1012 1167 1427 1825 589 5 6 7 1055 141 69 491 1545 487 739 1255...
output:
47813842
result:
ok 1 number(s): "47813842"
Test #28:
score: -100
Wrong Answer
time: 0ms
memory: 11832kb
input:
2000 241 410 1433 1627 1489 1395 611 1 2 3 2 3 3 1553 1507 1544 3 4 4 4 5 5 1073 1318 1088 112 333 87 1322 187 439 461 1272 1516 1385 813 1044 784 954 1186 449 53 531 5 6 6 644 1277 1454 76 1249 1631 1233 992 209 310 416 447 909 227 1268 956 594 1727 1576 1567 116 1954 1245 1988 1755 1154 437 1539 1...
output:
3241883560
result:
wrong answer 1st numbers differ - expected: '-1', found: '3241883560'