QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #722748 | #8760. 不等式 | Vocal# | ML | 1ms | 9840kb | C++23 | 1.8kb | 2024-11-07 20:06:28 | 2024-11-07 20:06:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>q[200010];
pair<int,int>b[200010];
int vis[200010];
int d[200010];
int bj = 1;
int x[200010],y[200010],z[200010];
int dfs(int x) {
if( !bj )return 0;
if( q[x].size() == 0 ) {
b[x].first = 1;
return 1;
}
if( b[x].first ) {
return b[x].first+b[x].second;
}
int res = 0;
for(int i = 0;i < q[x].size(); ++i) {
vis[q[x][i]] = 1;
res = dfs(q[x][i]);
if( res > b[x].first ) {
b[x].second = b[x].first;
b[x].first = res;
}
else if( res > b[x].second )b[x].second = res;
if( b[x].first+b[x].second > 1000000000 ) {
bj = 0;
return 0;
}
}
return b[x].first+b[x].second;
}
signed main() {
int n,m;
cin >> n >>m;
for(int i = 1;i <= m; ++i) {
int u,v1,v2;
cin >> u >> v1 >> v2;
x[i] = u;
y[i] = v1;
z[i] = v2;
q[u].push_back(v1);
q[u].push_back(v2);
d[v1]++;
d[v2]++;
}
int ans = 0;
for(int i = 1;i <= n; ++i) {
if( !vis[i] ) {
vis[i] = 1;
dfs(i);
}
}
for(int i = 1;i <= n; ++i) {
ans += b[i].first+b[i].second,bj = min(bj,b[i].first);
if( b[x[i]].first+b[x[i]].second < b[y[i]].first+b[y[i]].second+ b[z[i]].first+b[z[i]].second) {
bj = 0;
break;
}
if( ans > 1000000000 ) {
bj = 0;
break;
}
}
if( bj && ans <= 1000000000 )cout << ans <<endl;
else cout << -1 << endl;
return 0;
}
// 13 10
// 1 2 3
// 1 3 4
// 2 5 6
// 3 7 8
// 5 10 11
// 6 10 11
// 7 10 11
// 8 10 11
// 4 8 9
// 12 9 13
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9776kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9840kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7652kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 9748kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7668kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 1ms
memory: 7668kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 0ms
memory: 9688kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 0ms
memory: 7712kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 1ms
memory: 9688kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 7756kb
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: 7664kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 9708kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 0ms
memory: 7792kb
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: 7704kb
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: 9688kb
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: 9696kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 1ms
memory: 7656kb
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: 7732kb
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: 0ms
memory: 9756kb
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: 7668kb
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: 9716kb
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: 7812kb
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: 7740kb
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: 1ms
memory: 7808kb
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: -100
Memory Limit Exceeded
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...