QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#218895	#7152. Tri-color spanning tree	SolitaryDream^#	AC ✓	769ms	4936kb	C++17	2.2kb	2023-10-18 20:14:27	2023-10-18 20:14:27

Judging History

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

[2023-10-18 20:14:27]
评测

测评结果：AC
用时：769ms
内存：4936kb

查看

[2023-10-18 20:14:27]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=45;
const int Mod=1e9+7;
ll Fast(ll x,int b=Mod-2) {
    ll t=1;
    for(; b; b>>=1,x=x*x%Mod) if(b&1) t=t*x%Mod;
    return t;
}
vector<ll> interpolation(vector<ll> y) {
    int n=y.size();
    vector<ll> u=y,ret(n),sum(n);
    ret[0]=u[0],sum[0]=1;
    FOR(i,1,n-1) {
        DOR(j,n-1,i) u[j]=(u[j]-u[j-1])*Fast(i)%Mod;
        DOR(j,i,1) {
            sum[j]=(-sum[j]*(i-1)+sum[j-1])%Mod;
            ret[j]=(ret[j]+sum[j]*u[i])%Mod;
        }
        sum[0]=-sum[0]*(i-1)%Mod;
        ret[0]=(ret[0]+sum[0]*u[i])%Mod;
    }
    return ret;
}
ll a[N][N],p[N][N];
ll det(int n) {
    ll r=1;
    FOR(i,1,n) {
        int p=i;
        FOR(j,i+1,n) if(a[j][i]) p=j;
        if(a[p][i]==0) return 0;
        if(p!=i) r*=-1;
        FOR(j,i,n) swap(a[i][j],a[p][j]);
        r=r*a[i][i]%Mod;
        ll inv=Fast(a[i][i]);
        FOR(j,i+1,n) DOR(k,n,i) a[j][k]=(a[j][k]-a[i][k]*inv%Mod*a[j][i])%Mod;
    }
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,g,b;
    cin >> n >> m >> g >> b;
    vector<tuple<int,int,int>> E;
    FOR(i,1,m) {
        int x,y,c;
        cin >> x >> y >> c;
        E.push_back({x,y,c});
    }
    FOR(i,0,n-1) {
        FOR(j,0,n-1) {
            memset(a,0,sizeof(a));
            for(auto [x,y,c]: E) {
                int v=1;
                if(c==2) v=i;
                if(c==3) v=j;
                a[x][y]-=v;
                a[y][x]-=v;
                a[x][x]+=v;
                a[y][y]+=v;
            }
            p[i][j]=det(n-1);
        }
    }
    FOR(i,0,n-1) {
        vector<ll> y(n);
        FOR(j,0,n-1) y[j]=p[i][j];
        y=interpolation(y);
        FOR(j,0,n-1) p[i][j]=y[j];
    }
    FOR(i,0,n-1) {
        vector<ll> y(n);
        FOR(j,0,n-1) y[j]=p[j][i];
        y=interpolation(y);
        FOR(j,0,n-1) p[j][i]=y[j];
    }
    ll res=0;
    FOR(i,0,g) FOR(j,0,b) {
        res=(res+p[i][j])%Mod;
    }
    if(res<0) res+=Mod;
    cout << res << '\n';
    return 0;
}

Source code, Language: C++17

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3644kb

input:

output:

result:

ok 1 number(s): "1"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3848kb

input:

output:

result:

ok 1 number(s): "10"

Test #3:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

output:

result:

ok 1 number(s): "39"

Test #4:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

output:

result:

ok 1 number(s): "7"

Test #5:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

output:

result:

ok 1 number(s): "40"

Test #6:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

output:

result:

ok 1 number(s): "13"

Test #7:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

output:

result:

ok 1 number(s): "0"

Test #8:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

output:

result:

ok 1 number(s): "40"

Test #9:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

output:

result:

ok 1 number(s): "32"

Test #10:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok 1 number(s): "74"

Test #11:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok 1 number(s): "2"

Test #12:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

output:

result:

ok 1 number(s): "7"

Test #13:

score: 0

Accepted

time: 1ms

memory: 3852kb

input:

output:

result:

ok 1 number(s): "621"

Test #14:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

output:

result:

ok 1 number(s): "3318"

Test #15:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

output:

result:

ok 1 number(s): "1039"

Test #16:

score: 0

Accepted

time: 1ms

memory: 3548kb

input:

output:

result:

ok 1 number(s): "6886"

Test #17:

score: 0

Accepted

time: 1ms

memory: 3552kb

input:

output:

result:

ok 1 number(s): "1698"

Test #18:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok 1 number(s): "4342"

Test #19:

score: 0

Accepted

time: 1ms

memory: 3832kb

input:

output:

result:

ok 1 number(s): "60"

Test #20:

score: 0

Accepted

time: 1ms

memory: 3636kb

input:

output:

result:

ok 1 number(s): "3787"

Test #21:

score: 0

Accepted

time: 1ms

memory: 3772kb

input:

output:

result:

ok 1 number(s): "1787"

Test #22:

score: 0

Accepted

time: 1ms

memory: 3572kb

input:

output:

result:

ok 1 number(s): "0"

Test #23:

score: 0

Accepted

time: 4ms

memory: 3768kb

input:

output:

result:

ok 1 number(s): "6610857"

Test #24:

score: 0

Accepted

time: 4ms

memory: 3636kb

input:

output:

195713537

result:

ok 1 number(s): "195713537"

Test #25:

score: 0

Accepted

time: 4ms

memory: 3516kb

input:

output:

82484006

result:

ok 1 number(s): "82484006"

Test #26:

score: 0

Accepted

time: 4ms

memory: 3552kb

input:

output:

446528417

result:

ok 1 number(s): "446528417"

Test #27:

score: 0

Accepted

time: 4ms

memory: 3636kb

input:

output:

result:

ok 1 number(s): "61819"

Test #28:

score: 0

Accepted

time: 2ms

memory: 3648kb

input:

output:

84392785

result:

ok 1 number(s): "84392785"

Test #29:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

output:

218244865

result:

ok 1 number(s): "218244865"

Test #30:

score: 0

Accepted

time: 4ms

memory: 3636kb

input:

output:

result:

ok 1 number(s): "4755701"

Test #31:

score: 0

Accepted

time: 4ms

memory: 3840kb

input:

output:

64087172

result:

ok 1 number(s): "64087172"

Test #32:

score: 0

Accepted

time: 4ms

memory: 3632kb

input:

output:

75364945

result:

ok 1 number(s): "75364945"

Test #33:

score: 0

Accepted

time: 91ms

memory: 3636kb

input:

40 80 16 12
1 5 3
22 9 1
38 32 3
10 28 2
37 3 2
8 38 3
11 15 2
35 19 1
3 38 1
10 18 3
35 10 3
18 23 2
9 21 1
36 29 1
17 31 1
33 18 3
22 21 3
32 13 2
39 21 2
22 33 2
3 33 1
32 28 2
28 11 1
3 7 3
6 20 1
22 24 3
7 1 2
27 23 3
12 37 3
22 1 1
27 11 1
39 2 3
34 33 3
1 14 2
18 9 1
18 29 2
39 27 3
32 23 2
1...

output:

46618078

result:

ok 1 number(s): "46618078"

Test #34:

score: 0

Accepted

time: 86ms

memory: 3632kb

input:

40 80 12 12
20 25 2
8 16 3
3 9 3
34 5 2
30 36 1
26 38 1
14 9 1
17 21 1
28 7 2
25 19 3
15 11 2
37 10 1
23 12 3
10 18 1
17 11 2
1 33 1
23 6 3
8 18 2
17 33 1
32 17 2
22 6 3
1 32 2
5 25 2
18 35 2
25 18 2
12 14 2
2 13 2
8 25 3
5 38 3
2 7 2
30 11 1
17 2 1
8 2 1
26 7 2
22 27 3
28 15 2
30 2 3
40 13 2
31 21 ...

output:

733297013

result:

ok 1 number(s): "733297013"

Test #35:

score: 0

Accepted

time: 88ms

memory: 3644kb

input:

output:

461131346

result:

ok 1 number(s): "461131346"

Test #36:

score: 0

Accepted

time: 86ms

memory: 3468kb

input:

40 80 14 12
16 36 1
33 35 2
10 11 3
32 36 3
19 20 1
21 7 1
15 33 3
36 35 3
16 22 3
2 15 3
13 14 2
32 17 1
4 26 2
6 38 3
19 18 3
3 40 3
6 39 3
6 35 2
32 2 2
10 32 1
1 18 2
28 12 2
27 37 1
28 22 1
19 13 2
12 28 3
14 35 2
39 11 1
19 22 1
2 19 1
22 3 3
28 11 2
28 2 3
20 4 3
39 20 1
22 11 3
25 30 1
33 30...

output:

678457037

result:

ok 1 number(s): "678457037"

Test #37:

score: 0

Accepted

time: 89ms

memory: 3520kb

input:

output:

909420262

result:

ok 1 number(s): "909420262"

Test #38:

score: 0

Accepted

time: 87ms

memory: 3568kb

input:

40 80 16 13
36 38 1
27 24 2
40 16 1
12 36 1
13 33 1
16 39 1
30 11 3
34 30 1
15 23 2
36 11 3
10 38 3
17 11 2
8 39 3
33 7 1
32 10 2
39 25 3
31 8 1
11 7 1
28 25 2
10 7 3
4 26 2
7 18 2
24 22 1
18 21 3
14 8 2
11 33 2
20 12 3
22 20 2
22 10 2
32 33 3
31 15 1
38 16 3
13 29 3
6 22 3
11 22 3
38 31 2
29 16 1
3...

output:

995630943

result:

ok 1 number(s): "995630943"

Test #39:

score: 0

Accepted

time: 92ms

memory: 3868kb

input:

40 80 16 12
6 40 1
25 26 3
8 26 1
14 27 1
26 3 3
31 16 2
8 33 2
22 3 2
3 38 2
18 13 3
17 7 3
35 23 3
33 18 1
4 38 1
26 29 2
9 28 3
23 27 3
27 10 1
15 2 1
40 35 3
18 32 3
7 25 3
33 40 1
25 4 3
3 27 1
16 5 2
35 20 1
9 2 1
13 3 3
4 38 3
23 21 2
34 16 3
27 38 2
29 27 2
4 26 1
40 27 1
7 19 3
20 7 2
2 16 ...

output:

119701092

result:

ok 1 number(s): "119701092"

Test #40:

score: 0

Accepted

time: 90ms

memory: 3564kb

input:

output:

263640306

result:

ok 1 number(s): "263640306"

Test #41:

score: 0

Accepted

time: 91ms

memory: 3628kb

input:

40 80 12 13
29 30 3
16 28 1
17 40 1
9 30 2
20 36 1
33 21 3
29 19 2
29 19 2
27 32 3
25 12 2
2 28 2
6 23 1
17 31 2
8 35 3
32 30 1
4 6 2
9 38 2
13 30 2
26 33 2
13 10 1
10 24 2
34 14 3
28 36 1
23 3 2
36 7 1
6 8 1
21 16 1
3 16 2
36 23 3
22 6 2
31 39 3
38 17 2
2 15 1
14 6 2
28 33 3
22 35 1
39 24 1
22 13 3...

output:

147170504

result:

ok 1 number(s): "147170504"

Test #42:

score: 0

Accepted

time: 90ms

memory: 3644kb

input:

40 80 14 13
28 31 2
30 32 3
31 25 1
35 36 2
6 39 2
36 22 1
9 7 2
20 38 2
25 29 3
19 20 3
7 8 2
39 8 1
20 24 3
3 6 1
9 40 3
29 19 2
10 13 3
37 33 2
1 38 1
25 30 3
19 15 3
40 12 3
24 7 3
24 1 3
38 28 3
5 7 1
18 29 2
4 6 1
9 7 2
22 30 1
8 23 2
38 1 3
33 34 1
32 29 1
1 32 2
10 22 3
17 9 1
19 32 1
23 12 ...

output:

297418878

result:

ok 1 number(s): "297418878"

Test #43:

score: 0

Accepted

time: 182ms

memory: 4732kb

input:

20 100000 4 4
13 19 3
9 18 2
12 13 2
20 2 2
4 1 2
13 18 3
19 14 2
20 17 2
14 17 2
1 8 1
9 2 3
17 18 1
4 5 3
8 15 1
10 1 1
2 1 3
16 10 2
15 1 2
1 5 3
10 18 3
19 1 1
14 13 2
18 10 2
7 12 1
13 1 2
6 9 1
15 13 2
4 8 3
16 10 1
17 16 3
20 2 2
9 4 3
1 11 1
4 18 1
3 2 1
3 5 3
12 1 3
13 8 3
1 6 3
5 2 1
11 9 ...

output:

973042182

result:

ok 1 number(s): "973042182"

Test #44:

score: 0

Accepted

time: 182ms

memory: 4796kb

input:

20 100000 3 7
20 15 3
2 8 3
1 12 3
2 20 3
12 15 3
16 14 3
14 2 1
4 5 1
3 13 1
13 2 3
6 16 2
2 10 2
15 14 2
16 5 1
4 14 2
20 14 3
20 7 2
3 9 2
1 20 3
2 4 2
18 20 3
20 5 3
4 16 1
9 12 2
5 9 2
19 11 2
5 1 2
20 18 1
12 16 1
13 17 3
8 1 1
18 8 2
12 9 3
6 13 3
19 14 1
13 14 1
1 18 3
4 3 1
13 11 2
18 17 3
...

output:

717230121

result:

ok 1 number(s): "717230121"

Test #45:

score: 0

Accepted

time: 181ms

memory: 4936kb

input:

20 100000 9 6
11 12 1
1 5 1
15 16 1
6 11 1
6 20 2
16 12 3
3 18 2
15 7 1
10 6 1
16 18 3
12 9 2
19 1 1
6 11 3
10 3 1
18 9 1
14 12 2
12 2 3
15 8 3
13 19 1
15 6 1
17 8 2
8 13 1
2 3 1
6 16 2
14 4 2
20 14 1
8 2 3
14 9 1
6 2 3
9 20 1
8 20 1
3 7 3
16 10 1
12 11 2
5 19 1
20 19 3
9 3 1
5 7 3
15 18 2
1 10 2
9 ...

output:

523302000

result:

ok 1 number(s): "523302000"

Test #46:

score: 0

Accepted

time: 183ms

memory: 4872kb

input:

20 100000 11 4
12 8 1
16 3 3
1 16 2
20 14 3
5 11 2
14 16 1
14 7 1
12 17 3
9 20 1
10 18 2
12 20 2
5 9 2
13 4 3
14 4 3
11 13 1
3 19 3
18 8 1
3 16 2
8 5 1
19 12 3
19 4 3
1 7 2
15 8 3
17 2 3
9 7 3
20 10 1
18 9 2
17 16 3
9 18 1
7 11 3
11 15 1
8 4 1
14 12 2
2 16 2
11 13 1
2 19 1
1 12 3
19 17 1
18 10 2
4 1...

output:

627312150

result:

ok 1 number(s): "627312150"

Test #47:

score: 0

Accepted

time: 182ms

memory: 4860kb

input:

20 100000 8 3
19 13 2
2 14 2
17 8 1
11 5 3
13 9 1
10 3 3
1 16 1
1 10 1
6 9 2
19 8 1
10 17 3
16 4 1
1 6 2
6 15 3
1 18 2
11 16 1
14 13 1
10 7 1
7 17 2
10 14 1
11 15 1
19 1 1
6 19 2
3 1 1
10 17 3
9 13 1
2 9 3
5 13 3
7 11 1
16 7 1
3 6 2
20 2 2
20 9 1
7 17 2
13 4 2
13 20 2
13 14 2
10 6 2
19 7 3
16 5 2
9 ...

output:

659093814

result:

ok 1 number(s): "659093814"

Test #48:

score: 0

Accepted

time: 184ms

memory: 4756kb

input:

20 100000 4 9
7 18 1
16 2 3
4 8 3
9 2 2
3 1 2
8 13 1
7 15 3
13 6 3
4 3 3
3 17 1
6 8 2
2 17 1
10 19 2
13 9 3
18 15 3
16 7 1
16 7 2
10 11 3
15 1 3
6 1 1
10 13 2
10 14 3
6 7 3
9 3 1
10 16 2
1 6 3
3 16 2
5 6 3
5 20 3
15 9 1
2 16 2
20 15 2
3 2 1
10 5 3
5 11 2
20 13 3
19 6 3
11 12 1
6 17 3
5 7 1
1 8 1
6 1...

output:

105251930

result:

ok 1 number(s): "105251930"

Test #49:

score: 0

Accepted

time: 178ms

memory: 4936kb

input:

20 100000 6 5
15 13 2
14 17 2
2 11 3
11 13 3
20 3 1
13 1 2
9 8 1
1 17 2
18 5 2
18 15 1
1 11 3
7 16 2
13 2 1
2 9 1
1 17 2
19 18 1
17 9 3
1 11 2
11 1 2
2 19 1
6 1 1
20 13 3
5 20 3
13 6 3
20 11 1
6 12 2
13 15 3
20 16 1
19 17 2
12 18 3
1 8 3
10 7 3
19 15 3
16 1 1
8 15 1
1 20 3
10 17 1
1 4 1
11 10 2
2 18...

output:

161220215

result:

ok 1 number(s): "161220215"

Test #50:

score: 0

Accepted

time: 183ms

memory: 4752kb

input:

20 100000 5 10
7 2 1
17 2 3
2 10 3
15 16 3
9 12 1
3 17 1
4 18 3
4 13 1
10 16 2
6 10 3
20 5 1
16 10 1
17 20 3
3 2 1
12 15 2
18 15 2
12 19 1
8 2 3
16 9 3
17 1 1
18 4 3
4 20 1
11 6 3
6 10 3
14 4 2
4 7 1
19 9 2
12 18 3
12 6 3
13 5 1
18 9 3
7 20 1
9 5 3
9 5 3
11 10 1
2 14 3
8 1 2
9 11 1
6 12 2
19 3 1
4 1...

output:

13239242

result:

ok 1 number(s): "13239242"

Test #51:

score: 0

Accepted

time: 178ms

memory: 4748kb

input:

20 100000 7 4
13 11 1
3 16 3
6 18 2
8 7 2
14 12 2
13 4 2
17 15 2
15 10 2
15 6 3
4 7 2
12 5 3
3 15 1
19 2 2
11 13 3
6 17 2
7 1 3
7 13 3
19 4 1
10 15 1
14 15 2
14 9 3
15 17 1
13 15 3
8 18 1
6 4 2
13 11 3
15 18 2
3 9 1
1 15 3
1 11 2
10 9 2
4 13 3
19 16 2
17 19 1
13 3 3
7 3 3
3 12 3
2 3 2
16 12 1
19 10 ...

output:

490005853

result:

ok 1 number(s): "490005853"

Test #52:

score: 0

Accepted

time: 188ms

memory: 4844kb

input:

20 100000 6 10
19 11 1
13 16 2
12 20 3
1 10 3
10 4 2
10 4 1
9 2 1
13 8 1
20 15 1
12 5 1
16 14 3
18 15 1
1 12 2
18 6 2
2 17 2
18 14 2
17 5 3
3 9 1
12 9 2
8 1 2
16 20 3
8 6 2
10 1 3
4 9 2
12 3 3
11 16 2
12 15 3
17 1 1
5 7 3
18 11 2
19 15 3
11 2 1
17 4 2
15 14 1
3 5 3
10 19 1
11 7 3
20 7 2
13 20 2
9 11...

output:

855483153

result:

ok 1 number(s): "855483153"

Test #53:

score: 0

Accepted

time: 761ms

memory: 4792kb

input:

40 100000 14 17
15 40 1
26 27 1
35 13 1
5 32 1
13 38 1
22 20 3
9 10 1
14 39 2
38 33 1
30 8 3
10 36 1
8 2 1
34 24 3
37 10 3
40 36 1
21 13 2
29 21 2
4 13 3
28 15 3
39 37 2
29 22 2
30 11 1
4 39 1
28 5 2
4 14 3
26 37 1
3 26 1
37 20 2
27 23 2
39 30 2
31 10 2
36 6 2
14 17 2
29 14 1
17 25 3
35 36 2
9 11 1
...

output:

460711046

result:

ok 1 number(s): "460711046"

Test #54:

score: 0

Accepted

time: 764ms

memory: 4912kb

input:

40 100000 15 11
13 24 3
38 39 1
12 34 2
22 35 2
2 3 2
13 39 1
39 10 1
19 24 3
8 38 1
7 3 2
25 4 1
34 7 2
34 15 2
16 11 2
15 23 1
11 15 3
26 29 2
8 37 1
16 33 2
8 10 3
8 29 3
13 19 1
30 40 3
4 26 2
5 36 1
3 28 3
22 37 3
6 18 3
21 10 3
10 1 2
34 3 3
14 38 2
21 32 3
32 23 1
14 28 3
2 13 1
36 28 1
4 11 ...

output:

447107860

result:

ok 1 number(s): "447107860"

Test #55:

score: 0

Accepted

time: 757ms

memory: 4764kb

input:

40 100000 13 18
10 23 3
3 22 2
14 36 1
31 30 2
1 29 3
35 38 3
6 23 3
6 29 2
10 20 1
18 29 2
4 11 3
37 10 3
34 4 1
14 35 1
28 32 2
5 27 3
8 28 2
34 20 1
6 10 3
22 15 2
36 22 2
7 28 1
30 21 3
9 22 3
32 1 1
1 25 2
24 14 2
18 21 2
11 26 2
16 19 1
21 31 1
7 12 1
13 21 2
25 15 1
24 32 1
34 32 1
25 7 2
6 2...

output:

807926058

result:

ok 1 number(s): "807926058"

Test #56:

score: 0

Accepted

time: 755ms

memory: 4928kb

input:

40 100000 14 16
23 1 3
20 17 2
9 38 3
9 35 1
1 2 1
38 10 3
15 3 3
9 4 1
39 36 2
12 37 1
37 21 1
21 6 2
10 7 3
12 22 1
30 14 2
24 6 3
20 33 1
39 13 2
17 32 1
28 32 1
36 18 3
34 9 1
33 26 3
39 33 1
31 9 3
35 32 1
33 25 3
17 11 1
10 38 2
33 18 1
7 19 3
5 4 1
19 26 2
10 40 2
7 14 2
9 40 1
31 12 2
28 19 ...

output:

615635961

result:

ok 1 number(s): "615635961"

Test #57:

score: 0

Accepted

time: 763ms

memory: 4868kb

input:

40 100000 18 12
35 30 1
5 17 1
5 31 1
38 29 2
15 30 3
16 14 2
7 10 1
18 38 2
11 37 1
29 20 3
9 8 2
34 19 1
6 1 2
24 38 3
13 12 3
7 13 1
14 2 3
2 27 3
17 24 1
4 21 2
39 26 1
8 26 2
31 38 2
15 4 2
19 4 2
15 25 2
1 28 3
30 25 1
4 30 3
13 12 2
26 13 1
19 2 1
26 8 2
8 26 1
14 5 2
40 9 1
20 27 2
11 15 2
3...

output:

309519760

result:

ok 1 number(s): "309519760"

Test #58:

score: 0

Accepted

time: 752ms

memory: 4868kb

input:

40 100000 12 15
5 13 1
6 38 2
24 4 2
7 38 1
25 38 2
4 9 2
20 33 2
7 19 3
7 32 2
12 18 1
22 18 1
38 11 3
11 23 3
14 11 2
18 27 2
32 4 3
2 40 3
8 9 2
2 12 2
20 10 3
33 16 3
36 23 2
16 5 1
26 15 2
3 11 3
34 37 1
9 4 1
13 40 3
26 28 3
31 2 1
8 4 1
10 23 3
19 30 3
4 7 3
21 4 3
2 4 1
7 14 3
27 40 3
13 16 ...

output:

752864274

result:

ok 1 number(s): "752864274"

Test #59:

score: 0

Accepted

time: 769ms

memory: 4800kb

input:

40 100000 17 10
15 36 2
27 33 2
4 3 2
11 27 1
22 40 2
22 40 2
34 19 3
7 34 3
39 10 3
12 13 3
3 9 3
3 10 1
32 24 2
12 32 3
31 4 2
24 14 2
31 1 1
35 23 3
40 24 2
1 3 2
2 38 1
25 1 3
14 12 1
25 3 1
26 22 1
35 29 2
27 33 3
10 5 3
33 9 1
1 33 1
1 29 2
8 3 2
1 33 1
6 26 3
9 6 3
8 28 1
38 34 3
3 21 2
27 23...

output:

786436519

result:

ok 1 number(s): "786436519"

Test #60:

score: 0

Accepted

time: 766ms

memory: 4916kb

input:

40 100000 13 13
38 36 3
26 12 1
24 26 3
14 27 1
40 11 3
12 31 3
10 27 3
10 5 1
14 4 3
7 37 3
35 38 2
33 15 1
22 32 2
1 2 3
17 32 1
31 7 1
8 33 3
38 2 3
2 14 2
36 32 2
21 13 2
37 1 2
2 13 2
27 31 2
28 32 3
37 25 1
10 2 1
8 24 3
11 24 2
22 13 3
37 15 2
15 35 1
2 25 3
8 5 2
23 18 3
30 34 3
16 12 3
16 3...

output:

664442650

result:

ok 1 number(s): "664442650"

Test #61:

score: 0

Accepted

time: 759ms

memory: 4932kb

input:

40 100000 9 12
35 16 2
16 34 2
37 39 3
8 39 1
38 9 2
31 13 2
32 10 1
4 5 3
6 33 3
23 10 2
19 8 3
37 34 1
31 26 3
11 10 2
18 32 2
30 12 3
38 19 2
29 6 1
40 1 1
39 6 3
22 19 2
2 11 1
4 33 1
22 26 1
20 17 2
34 6 3
38 11 2
40 26 1
23 12 2
13 34 2
5 14 3
29 3 2
28 9 1
16 7 2
8 37 1
4 34 1
34 26 3
37 33 3...

output:

729894507

result:

ok 1 number(s): "729894507"

Test #62:

score: 0

Accepted

time: 759ms

memory: 4864kb

input:

40 100000 15 12
27 33 1
3 29 2
8 29 1
3 40 1
37 19 1
36 12 3
16 40 2
5 34 3
11 18 2
21 31 3
7 16 1
37 7 3
38 18 3
2 28 2
36 38 2
16 34 1
4 24 3
25 35 2
30 20 3
20 39 2
38 25 2
40 3 3
37 29 3
5 35 3
4 22 3
23 30 3
6 27 2
12 1 2
16 17 3
10 15 1
24 29 3
17 6 1
39 4 2
31 18 3
19 5 1
37 13 3
3 40 3
8 23 ...

output:

507681852

result:

ok 1 number(s): "507681852"

Extra Test:

score: 0

Extra Test Passed