QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#669585 | #8760. 不等式 | HQLF | ML | 2ms | 5488kb | C++20 | 2.4kb | 2024-10-23 19:05:37 | 2024-10-23 19:05:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ldb=long double;
using ull=unsigned long long;
const long long inf=0x3f3f3f3f3f3f3f3f;
using i128=__int128;
const int mod=1000000007;
const long double eps=0.00000000001;
struct DSU
{
vector<int>f,siz;
DSU() {}
DSU(int n)
{
init(n);
}
void init(int n)
{
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x)
{
while(x!=f[x])
{
x=f[x]=f[f[x]];
}
return 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];
f[y]=x;
return true;
}
int size(int x)
{
return siz[find(x)];
}
};
vector<pair<int,int>>a[300010];
i128 ans[300010];
DSU c{300010};
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++)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=c.find(x);
if(fax==y)f=-1;
if(fax==z)f=-1;
c.merge(x,y);
c.merge(x,z);
a[x].push_back({y,z});
}
if(f==-1)
{
printf("-1\n");
return;
}
for(int i=1;i<=n;i++)
{
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;
// cin>>_;
while(_--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 5208kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5360kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 5176kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 2ms
memory: 5488kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 2ms
memory: 5376kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 2ms
memory: 5228kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 2ms
memory: 5308kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 0ms
memory: 5204kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 0ms
memory: 5344kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 2ms
memory: 5360kb
input:
5 2 1 2 3 2 3 4
output:
8
result:
ok 1 number(s): "8"
Test #11:
score: 0
Accepted
time: 2ms
memory: 5404kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 5364kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 0ms
memory: 5360kb
input:
10 2 1 2 3 2 3 4
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 2ms
memory: 5212kb
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: 5172kb
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: 5360kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 2ms
memory: 5168kb
input:
20 2 1 2 3 2 3 3
output:
23
result:
ok 1 number(s): "23"
Test #18:
score: 0
Accepted
time: 2ms
memory: 5356kb
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: 2ms
memory: 5388kb
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: 2ms
memory: 5368kb
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: 0ms
memory: 5360kb
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: 2ms
memory: 5220kb
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: 2ms
memory: 5408kb
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: 2ms
memory: 5224kb
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...