QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#669585#8760. 不等式HQLFML 2ms5488kbC++202.4kb2024-10-23 19:05:372024-10-23 19:05:37

Judging History

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

  • [2024-10-23 19:05:37]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:5488kb
  • [2024-10-23 19:05:37]
  • 提交

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...

output:


result: