QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226878#5411. 杏仁chenxinyang2006100 ✓3011ms273520kbC++145.9kb2023-10-26 17:38:092023-10-26 17:38:10

Judging History

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

  • [2023-10-26 17:38:10]
  • 评测
  • 测评结果：100
  • 用时：3011ms
  • 内存：273520kb
查看
  • [2023-10-26 17:38:09]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}
Z fact[1000005],ifac[1000005],inv[1000005];

Z C(int N,int M){
    if(N < M || M < 0) return 0;
    return fact[N] * ifac[M] * ifac[N - M];
}

void init(int L){
    fact[0] = 1;
    rep(i,1,L) fact[i] = fact[i - 1] * i;
    ifac[L] = 1 / fact[L];
    per(i,L - 1,0) ifac[i] = ifac[i + 1] * (i + 1);
    rep(i,1,L) inv[i] = ifac[i] * fact[i - 1];
}
int n,m,N,s,t,q,ext;
int val[25][25],id[25];
Z a[25],b[25];

Z dp[1 << 20][20];

Z f[21][1 << 20],g[21][1 << 20],res[1 << 20];
void FWT(Z *F){
    rep(i,0,n - 1){
        rep(S,0,(1 << n) - 1) if((S >> i) & 1) F[S] += F[S - (1 << i)];
    }
}

void iFWT(Z *F){
    rep(i,0,n - 1){
        rep(S,0,(1 << n) - 1) if((S >> i) & 1) F[S] -= F[S - (1 << i)];
    }
}

Z F[21],G[21],ans[21];
int main(){
//    freopen("test.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    init(n);
    N = 0;
    rep(u,1,n){
        if(u == s || u == t) continue;
        id[u] = N++;
    }

    rep(i,1,m){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u == s && v == t){
            ext++;
            continue;
        }
        if(v == s || u == t) continue;

        if(u == s) a[id[v]]++;
        else if(v == t) b[id[u]]++;
        else val[id[u]][id[v]]++;
    }

    n = N;
    rep(S,1,(1 << n) - 1){
        if(popcnt(S) == 1){
            int u = __lg(S);
            dp[S][u] = b[u];
            f[popcnt(S)][S] += a[u] * b[u];
            continue;
        }
        Z temp = 0;
        rep(u,0,n - 1){
            if(!((S >> u) & 1)) continue;
            int R = S - (1 << u);
            rep(v,0,n - 1) if((R >> v) & 1) dp[S][u] += val[u][v] * dp[R][v];
            temp += a[u] * dp[S][u];
        }
        f[popcnt(S)][S] += temp;
//        printf("%d %d\n",S,temp.val());
    }
/*    printf("A:\n");
    rep(i,0,n - 1) printf("%d ",a[i].val());
    printf("\n");
    printf("B:\n");
    rep(i,0,n - 1) printf("%d ",b[i].val());
    printf("\n");
    rep(u,0,n - 1){
        rep(v,0,n - 1) printf("%d ",val[u][v]);
        printf("\n");
    }*/
    rep(i,1,n) FWT(f[i]);

    rep(S,0,(1 << n) - 1){
        rep(i,0,n) F[i] = f[i][S];
        G[0] = 1;
        rep(i,0,n - 1){
            G[i + 1] = 0;
            rep(j,0,i) G[i + 1] += (j + 1) * F[j + 1] * G[i - j];
            G[i + 1] *= inv[i + 1];
        }
        rep(i,0,n) g[i][S] = G[i];
    }
    rep(i,1,n) iFWT(g[i]);
    rep(S,0,(1 << n) - 1) res[S] = g[popcnt(S)][S];

    FWT(res);
    rep(S,0,(1 << n) - 1){
        rep(u,0,n - 1) ans[u] += dp[S][u] * a[u] * res[(1 << n) - 1 - S];
    }

    scanf("%d",&q);
    rep(i,1,q){
        int u;
        scanf("%d",&u);
        if(u == t) printf("%d\n",(res[(1 << n) - 1] * (power(2,ext) - 1)) .val());
        else printf("%d\n",(ans[id[u]] * power(2,ext)).val());
    }
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 7ms
memory: 273416kb

input:

5 10
1 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
4
2
3
4
5

output:

20
14
10
15

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 8ms
memory: 273340kb

input:

2 0
1 2
0

output:

result:

ok 0 lines

Test #3:

score: 0
Accepted
time: 16ms
memory: 273396kb

input:

4 20
1 4
1 4
2 4
1 4
2 4
1 1
3 4
3 1
2 4
1 3
1 3
3 2
2 3
4 1
3 1
2 3
1 4
3 2
4 4
3 1
1 4
4
2
4
3
2

output:

0
225
224
0

result:

ok 4 lines

Test #4:

score: 0
Accepted
time: 14ms
memory: 273392kb

input:

5 20
1 5
1 5
1 2
4 2
5 3
1 1
1 4
4 5
5 1
1 3
2 5
2 4
3 1
5 2
4 3
4 3
3 4
5 1
4 2
4 5
3 4
5
3
4
2
5
5

output:

24
12
18
22
22

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 11ms
memory: 273352kb

input:

6 20
4 5
4 5
4 1
5 3
2 6
3 5
3 5
5 3
1 4
2 5
4 5
3 5
1 3
3 5
4 2
4 4
3 5
6 5
1 6
5 6
4 4
6
2
3
5
6
1
3

output:

52
0
60
0
68
0

result:

ok 6 lines

Test #6:

score: 0
Accepted
time: 11ms
memory: 273492kb

input:

11 20
3 1
3 1
3 7
9 1
4 9
7 4
9 11
6 11
9 5
3 5
3 7
8 9
1 7
10 1
6 11
11 5
3 7
8 10
7 1
9 7
11 8
10
2
10
7
8
11
1
6
9
5
1

output:

0
0
18
0
0
10
0
0
0
10

result:

ok 10 lines

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 10
Accepted
time: 7ms
memory: 273468kb

input:

11 9728
6 10
6 10
9 10
5 10
6 4
4 10
1 6
8 10
3 8
1 10
9 7
5 3
6 4
6 5
11 6
9 6
6 6
3 10
2 4
2 11
6 10
6 2
6 5
10 6
2 10
11 2
9 10
1 10
9 10
7 8
3 1
8 3
3 7
9 11
2 9
6 4
10 11
8 4
2 10
11 10
6 3
6 10
6 11
1 11
6 9
7 11
8 3
9 7
2 1
11 2
6 2
4 1
3 10
6 6
6 11
3 2
10 10
7 10
7 10
6 6
6 8
4 3
4 10
4 2
1...

output:

18074853
107213401
341119309
102827400
474349010
797006791
628391650
336670841
867783896
401391226
341119309

result:

ok 11 lines

Test #8:

score: 0
Accepted
time: 16ms
memory: 273392kb

input:

11 9613
4 1
4 1
8 9
11 1
7 8
4 10
2 1
6 11
4 2
11 9
5 7
11 6
2 6
11 2
3 9
3 9
1 1
6 3
1 6
3 1
2 1
10 5
4 9
4 2
10 1
7 8
6 8
3 1
9 11
4 9
5 1
1 7
11 3
10 8
8 11
2 9
3 1
7 1
8 1
7 8
4 4
4 7
3 7
1 1
6 1
4 6
5 1
8 7
4 4
1 6
4 9
4 11
5 3
10 7
7 2
6 5
4 9
4 9
8 7
5 1
4 1
1 1
4 6
11 1
3 7
8 11
6 1
1 10
8 4...

output:

182705163
786446186
459586140
963615780
865915814
315502014
910204714
865915814
514046009
72155443
281775231

result:

ok 11 lines

Test #9:

score: 0
Accepted
time: 18ms
memory: 273416kb

input:

11 9669
10 6
10 6
10 7
10 9
2 6
4 6
10 6
10 6
11 1
3 9
4 10
1 8
9 11
3 9
3 5
1 6
11 7
4 6
2 11
3 6
6 7
3 5
8 11
6 11
3 10
10 9
8 2
2 8
11 3
10 7
3 6
10 9
3 6
5 7
11 8
8 6
7 11
4 2
4 3
3 5
6 1
10 1
11 4
10 11
3 8
6 8
10 7
3 2
1 6
3 9
3 2
6 3
9 2
10 2
5 8
7 6
11 3
10 3
8 4
2 3
10 5
10 8
9 4
4 3
5 6
10...

output:

149327198
149327198
621010244
313847170
72070176
640755787
768354631
327768688
860362353
839515336
716753550

result:

ok 11 lines

Test #10:

score: 0
Accepted
time: 19ms
memory: 273468kb

input:

11 9989
8 4
8 4
8 10
6 3
5 4
3 10
8 5
1 6
2 4
7 4
3 2
5 8
11 4
11 4
8 5
9 1
5 8
11 3
8 4
8 4
4 3
3 4
8 1
2 3
11 9
3 6
2 11
8 6
4 10
5 4
3 5
5 4
10 3
5 11
9 6
8 4
1 10
2 7
11 3
8 11
2 3
2 11
7 4
2 6
8 1
8 4
8 11
2 9
9 1
8 9
5 4
8 8
3 4
9 11
8 5
8 2
6 2
9 4
10 1
8 4
10 2
5 8
8 4
8 4
10 6
8 4
2 1
10 4
...

output:

925008018
925008018
417424703
233031232
592456114
905513142
507449485
987584281
67045289
93256542
679477325

result:

ok 11 lines

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 15
Accepted
time: 71ms
memory: 273344kb

input:

17 9734
12 7
12 7
12 13
12 17
12 13
5 6
9 15
12 4
12 17
8 5
7 3
12 15
7 11
5 9
6 3
2 1
5 3
12 14
8 14
13 1
12 17
8 5
1 7
10 7
1 3
17 4
12 13
4 9
12 11
12 15
12 2
10 7
2 7
15 17
15 16
11 2
2 9
9 13
12 13
10 16
12 4
9 7
6 8
10 3
12 9
14 1
4 11
12 5
14 7
16 5
13 7
1 7
5 9
12 1
3 16
10 1
5 11
3 6
9 1
12...

output:

495528391
190001284
700736504
375686904
65816767
495528391
159308841
716930343
767343668
644562391
605875454
655781543
517152891
728480649
862738224
186485114
473518401

result:

ok 17 lines

Test #12:

score: 0
Accepted
time: 71ms
memory: 273420kb

input:

17 9672
15 6
15 6
4 12
15 3
6 4
8 6
15 1
1 6
15 3
6 3
9 10
15 6
8 12
1 5
13 6
1 10
13 1
3 6
17 10
15 6
14 6
15 15
15 12
6 17
7 17
15 10
10 14
10 1
9 16
9 6
9 3
10 3
15 12
10 15
11 17
8 6
15 6
14 16
13 7
15 5
1 6
6 8
5 3
13 6
4 16
12 6
15 10
2 13
9 6
10 12
11 6
4 16
15 17
8 6
15 13
12 6
2 6
16 6
14 8...

output:

279235714
30374151
24538748
679469233
229435792
155945081
450016612
514325705
338303999
985948696
888015758
183228636
644327192
941925587
178117228
380944360

result:

ok 16 lines

Test #13:

score: 0
Accepted
time: 55ms
memory: 273428kb

input:

17 9211
2 5
2 5
9 2
12 5
7 3
17 5
8 10
4 5
5 7
2 6
1 6
13 15
2 3
4 2
16 5
10 5
17 5
10 5
12 5
2 8
2 13
2 8
16 5
16 17
13 6
6 5
13 9
2 13
9 5
16 4
1 3
9 8
5 8
13 8
13 8
17 9
12 8
2 7
8 12
3 5
2 2
2 6
5 10
17 16
15 8
6 5
7 2
2 5
5 13
2 11
3 12
11 17
2 1
3 1
5 5
16 5
14 1
14 3
2 5
2 11
1 2
11 17
8 17
1...

output:

908804301
908804301
307393040
186849899
781252717
119888384
204862051
534656059
895145247
661847250
924518557
467036885
58336416
491807201
908827619
558794051
946875930

result:

ok 17 lines

Test #14:

score: 0
Accepted
time: 59ms
memory: 273428kb

input:

17 9419
6 4
6 4
12 8
12 7
6 14
5 8
13 17
6 2
15 3
16 17
4 11
8 15
6 10
2 9
5 15
6 7
9 15
7 9
16 17
6 9
4 9
13 4
17 3
6 4
17 1
1 4
6 13
1 13
6 15
6 14
15 4
8 10
12 13
6 15
12 4
6 11
8 11
6 11
10 4
4 13
6 1
8 9
6 3
10 4
16 4
6 15
7 4
8 12
6 2
13 4
6 6
2 4
3 14
6 4
17 9
15 1
10 4
5 6
16 4
6 13
17 4
9 4...

output:

594645673
313755086
496861206
822384794
781137812
81453666
4716276
155386775
58356574
571636304
756397369
43308328
933629703
283926473
785522930
781137812
210317775

result:

ok 17 lines

Subtask #4:

score: 10
Accepted

Test #15:

score: 10
Accepted
time: 78ms
memory: 273396kb

input:

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

output:

256104819
256104819
238677015
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819

result:

ok 18 lines

Test #16:

score: 0
Accepted
time: 366ms
memory: 273400kb

input:

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

output:

681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066
205106617
681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066

result:

ok 20 lines

Test #17:

score: 0
Accepted
time: 774ms
memory: 273472kb

input:

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

output:

689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
319626977
689426186
689426186
689426186
689426186
689426186
689426186
689426186

result:

ok 21 lines

Test #18:

score: 0
Accepted
time: 1729ms
memory: 273520kb

input:

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

output:

761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899
761174899

result:

ok 16 lines

Subtask #5:

score: 15
Accepted

Dependency #3:

100%
Accepted

Test #19:

score: 15
Accepted
time: 625ms
memory: 273348kb

input:

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

output:

179347313
813550320
55541421
405489637
801544214
265335425
90067137
626644771
626644771
615808650
632719968
841656106
550489038
45226589
213407794
395806519
252306265
749721021

result:

ok 18 lines

Test #20:

score: 0
Accepted
time: 633ms
memory: 273420kb

input:

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

output:

386683584
981197584
295067952
959466383
367406281
904970396
60926169
680079950
140257013
799282231
942493710
526069741
295067952
253472822
547817557
133654323
88470401
166618598
859311346
123497025

result:

ok 20 lines

Test #21:

score: 0
Accepted
time: 630ms
memory: 273424kb

input:

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

output:

397556349
358810345
501146333
577334371
835876687
376127539
835876687
539927444
460497656
881120268
759048774
344862737
887967107
857863406
254070753
945686970
963556183
353304563
606281636
380091288

result:

ok 20 lines

Test #22:

score: 0
Accepted
time: 624ms
memory: 273348kb

input:

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

output:

957979960
833782465
40246276
99257626
590270776
980823052
268457110
796100603
227887423
611801938
57261363
673239257
72751360
867945415
138029821
212647825
212647825
321330753
872345561
531961456

result:

ok 20 lines

Subtask #6:

score: 15
Accepted

Test #23:

score: 15
Accepted
time: 2991ms
memory: 273348kb

input:

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

output:

667211711

result:

ok single line: '667211711'

Test #24:

score: 0
Accepted
time: 2997ms
memory: 273428kb

input:

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

output:

438165179

result:

ok single line: '438165179'

Test #25:

score: 0
Accepted
time: 2998ms
memory: 273492kb

input:

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

output:

549362840

result:

ok single line: '549362840'

Test #26:

score: 0
Accepted
time: 2994ms
memory: 273408kb

input:

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

output:

326090706

result:

ok single line: '326090706'

Subtask #7:

score: 25
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #27:

score: 25
Accepted
time: 3011ms
memory: 273420kb

input:

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

output:

869110399
741906777
872128879
216648639
415599245
875131101
897256727
995298847
35784582
234345695
391030282
884094229
754548134
360237068
770196991
561636868
869110399
517825413
447157277
504632865
37906417
368706206

result:

ok 22 lines

Test #28:

score: 0
Accepted
time: 3006ms
memory: 273472kb

input:

22 9503
22 3
22 3
8 3
13 6
22 19
6 11
13 15
3 19
17 20
10 1
18 3
16 3
22 14
10 3
5 2
15 19
22 20
8 20
4 15
2 19
11 5
20 15
18 3
22 17
22 14
22 12
10 3
21 14
5 3
22 1
17 11
4 12
19 3
3 14
16 17
11 8
17 2
21 16
18 19
22 14
22 4
16 3
10 3
17 8
22 22
12 10
14 3
18 5
21 20
14 11
22 20
15 20
6 17
3 3
15 1...

output:

464398580
282832880
712555046
820396462
450478874
647786835
710010046
877576444
198665939
405003295
654044681
952154654
10240690
288607482
198665939
532817884
161403766
891549028
484235068
955844848
270266314

result:

ok 21 lines

Test #29:

score: 0
Accepted
time: 2983ms
memory: 273476kb

input:

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

output:

814824976
898909419
746959994
823736122
581817506
531540639
160720095
552006926
834344603
116262213
423845668
717321704
614461048
991501489
854901983
452113174
540794298
880984197
930938054
898909419
424285080

result:

ok 21 lines

Test #30:

score: 0
Accepted
time: 3006ms
memory: 273416kb

input:

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

output:

299327417
183877516
688009552
836668691
56551088
570118366
253931420
95629600
423301081
535031824
233945909
709673095
359804873
839231694
897143160
333241007
335944871
381607195
688009552
753685745
678759887

result:

ok 21 lines
English 繁體中文 简体中文

Server Time: 2024-12-02 15:39:07 | OpenSource Project