QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #669811 | #8760. 不等式 | zwu2021016337 | ML | 1ms | 6012kb | C++20 | 2.1kb | 2024-10-23 19:44:52 | 2024-10-23 19:44:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const long long inf=0x3f3f3f3f3f3f3f3f;
using i128 = __int128;
int fa[200010];
int siz[200010];
int find(int x)
{
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[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];
fa[y]=x;
return true;
}
int size(int x)
{
return siz[find(x)];
}
vector<pair<int,int>>a[200010];
i128 ans[200010];
int f=0;
void dfs(int p)
{
if(f==-1)return;
if(a[p].empty())
{
ans[p]=1;
return;
}
int la=(int)a[p].size();
i128 mx=-inf;
for(int i=0;i<=la-1;i++)
{
int x=a[p][i].first;
int y=a[p][i].second;
if(ans[x]==-1)dfs(x);
if(ans[y]==-1)dfs(y);
mx=max(mx,ans[x]+ans[y]);
}
if(mx>1000000000)f=-1;
else ans[p]=mx;
}
void solve()
{
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++)
{
fa[i]=i;
siz[i]=1;
}
for(int i=0;i<=n;i++)ans[i]=-1;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
if(x==y||x==z)f=-1;
int fax=find(x);
if(fax==y)f=-1;
if(fax==z)f=-1;
if(f!=-1)
{
merge(x,y);
merge(x,z);
a[x].push_back({y,z});
}
else continue;
}
if(f==-1)
{
printf("-1\n");
return;
}
for(int i=1;i<=n;i++)
{
if(ans[i]==-1)dfs(i);
if(f==-1)
{
printf("-1\n");
return;
}
}
i128 sum=0;
for(int i=1;i<=n;i++)
{
sum+=ans[i];
if(sum>1000000000)
{
printf("-1\n");
return;
}
}
printf("%lld\n",(ll)sum);
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
ll _=1;
while(_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5976kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5808kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 1ms
memory: 6012kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5900kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
5 2 1 2 3 2 3 4
output:
8
result:
ok 1 number(s): "8"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 1ms
memory: 5800kb
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: 5792kb
input:
10 2 1 2 2 2 3 4
output:
14
result:
ok 1 number(s): "14"
Test #15:
score: 0
Accepted
time: 1ms
memory: 5800kb
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: 5972kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 1ms
memory: 5812kb
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: 3772kb
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: 5748kb
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: 3824kb
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: 3780kb
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: 5880kb
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: 5876kb
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: 5952kb
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...