QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734738#8760. 不等式swan416#WA 0ms4108kbC++202.3kb2024-11-11 14:43:072024-11-11 14:43:07

Judging History

你现在查看的是最新测评结果

  • [2024-11-11 14:43:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4108kb
  • [2024-11-11 14:43:07]
  • 提交

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'