QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#734738 | #8760. 不等式 | swan416# | WA | 0ms | 4108kb | C++20 | 2.3kb | 2024-11-11 14:43:07 | 2024-11-11 14:43:07 |
Judging History
answer
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
int n,m;
scanf("%d%d",&n,&m);
vector<int> out[n+1],in[n+1];
int out_cnt[n+1],in_cnt[n+1];
memset(out_cnt,0,sizeof(out_cnt));
memset(in_cnt,0,sizeof(in_cnt));
vector<tuple<int,int,int>> query;
for(int i=0;i<m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
query.push_back({x,y,z});
out[x].push_back(y);
out[x].push_back(z);
out_cnt[x]+=2;
in[y].push_back(x);
in_cnt[y]++;
in[z].push_back(x);
in_cnt[z]++;
}
queue<int> q;
for(int i=1;i<=n;i++)
{
if(in_cnt[i]==0)
{
q.push(i);
}
}
while(q.size())
{
int x=q.front();
q.pop();
for(int y:out[x])
{
in_cnt[y]--;
if(in_cnt[y]==0)
{
q.push(y);
}
}
}
for(int i=1;i<=n;i++)
{
if(in_cnt[i]>0)
{
printf("-1\n");
return ;
}
}
auto cmp=[&](tuple <int,int,int> a,tuple <int,int,int> b)
{
tuple<int,int,int> x,y;
x={out_cnt[get<1>(a)],out_cnt[get<2>(a)],out_cnt[get<0>(a)]};
y={out_cnt[get<1>(b)],out_cnt[get<2>(b)],out_cnt[get<0>(b)]};
return x<y;
};
sort(query.begin(),query.end(),cmp);
ll value[n+1];
memset(value,0,sizeof(value));
for(int i=1;i<=n;i++)
{
if(out_cnt[i]==0)
value[i]=1;
}
for(int i=0;i<m;i++)
{
int x,y,z;
// printf("%d %d %d\n",get<0>(query[i]),get<1>(query[i]),get<2>(query[i]));
tie(x,y,z)=query[i];
value[x]=max(value[x],value[y]+value[z]);
// printf("so I change the value of %d to %lld\n",x,value[x]);
}
ll ans=0;
for(int i=1;i<=n;i++)
{
// printf("%lld ",value[i]);
ans+=value[i];
}
// printf("\n");
if(ans>1e9)
{
printf("-1\n");
}
else
{
printf("%lld\n",ans);
}
}
int main()
{
int T=1;
//scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3800kb
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: 3748kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3800kb
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: 4104kb
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: 4108kb
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: 3800kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
20 2 1 2 3 2 3 3
output:
23
result:
ok 1 number(s): "23"
Test #18:
score: 0
Accepted
time: 0ms
memory: 4096kb
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: 4024kb
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: 0ms
memory: 3788kb
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: -100
Wrong Answer
time: 0ms
memory: 3812kb
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:
202
result:
wrong answer 1st numbers differ - expected: '318', found: '202'