oj.uz

Submission #588383

# Submission time Handle Problem Language Result Execution time Memory
588383 2022-07-03T08:49:54 Z 79brue Star Trek (CEOI20_startrek) C++17
30 / 100
 1000 ms 30400 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

struct Matrix{
    int n, m;
    ll mat[2][2];
    Matrix(){}
    Matrix(int n, int m): n(n), m(m){
        for(int i=0; i<n; i++) for(int j=0; j<m; j++) mat[i][j] = 0;
    }

    Matrix operator*(const Matrix &r)const{
        assert(m == r.n);
        Matrix ret (n, r.m);
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                for(int k=0; k<r.m; k++){
                    ret.mat[i][k] += mat[i][j] * r.mat[j][k];
                    ret.mat[i][k] %= MOD;
                }
            }
        }
        return ret;
    }
};

ll mpow(ll x, ll y){
    if(!y) return 1;
    if(y%2) return mpow(x, y-1) * x % MOD;
    ll tmp = mpow(x, y/2);
    return tmp*tmp%MOD;
}

Matrix BasicMatrix(int n, int m){
    Matrix mat (n, m);
    assert(n==m);
    for(int i=0; i<n; i++) mat.mat[i][i] = 1;
    return mat;
}

Matrix mpow(Matrix x, ll y){
    if(!y) return BasicMatrix(x.n, x.m);
    if(y&1) return mpow(x, y-1) * x;
    Matrix tmp = mpow(x, y/2);
    return tmp * tmp;
}

ll n;
ll k;
vector<int> link[100002];
ll mat[400002];
int ex[400002], ey[400002];
int parEdge[400002];
bool canWin[400002];
bool dfsChk[400002], findChk[400002][2];

ll group[400002], groupCnt[2];
ll find1[400002][2];
ll res[400002];
ll ans;

void groupDfs(int x, int p=-1){
    groupCnt[group[x]]++;
    for(auto y: link[x]){
        if(ey[y]==p) continue;
        group[ey[y]] = !group[x];
        groupDfs(ey[y], x);
    }
}

bool dfs(int x, int pe){
    if(dfsChk[pe]) return mat[pe];
    dfsChk[pe] = 1;
    for(auto y: link[x]){
        if((y^pe)==1) continue;
        if(!dfs(ey[y], y)) mat[pe] = 1;
    }
    return mat[pe];
}

int dfsFind(int x, int pe, bool dp){ /// 무조건 지나야 하는 상대 차례 점 개수 찾기
    if(findChk[pe][dp]) return find1[pe][dp];
    findChk[pe][dp] = 1;
    if(!dp){ /// my turn
        int cnt = 0;
        for(auto y: link[x]){
            if((y^1)!=pe && !mat[y]) cnt++;
        }
        if(cnt > 1) return find1[pe][dp] = 0;
        assert(cnt == 1);
        for(auto y: link[x]){
            if((y^1)!=pe && !mat[y]) return find1[pe][dp] = dfsFind(ey[y], y, !dp);
        }
        exit(1);
    }
    else{ /// your turn
        int ret = 1;
        for(auto y: link[x]){
            if((y^1)==pe) continue;
            ret += dfsFind(ey[y], y, !dp);
        }
        return find1[pe][dp] = ret;
    }
}

int main(){
    scanf("%lld %lld", &n, &k);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(i*2-2);
        link[y].push_back(i*2-1);
        ex[i*2-2] = x, ey[i*2-2] = y;
        ex[i*2-1] = y, ey[i*2-1] = x;
    }
    for(int i=n; i<n+n; i++){
        ex[i*2-2] = -1, ey[i*2-2] = i-n+1;
        ex[i*2-1] = i-n+1, ey[i*2-1] = -1;
        parEdge[i-n+1] = i*2-2;
    }

    groupDfs(1);
    for(int i=1; i<=n; i++){
        canWin[i] = dfs(i, parEdge[i]);
        if(canWin[i]) res[i] = groupCnt[!group[i]] - dfsFind(i, parEdge[i], 0);
        else res[i] = dfsFind(i, parEdge[i], 1);
    }

    Matrix first (1, 2);
    first.mat[0][0] = first.mat[0][1] = 0;
    for(int i=1; i<=n; i++){
        if(canWin[i]) first.mat[0][0]++;
        else first.mat[0][1]++;
    }

    Matrix multiplier (2, 2); /// 0: WIN, 1: LOSE
    for(int i=1; i<=n; i++){
        if(canWin[i]){
            multiplier.mat[0][0] = (multiplier.mat[0][0] + n) % MOD;
            multiplier.mat[1][0] = (multiplier.mat[1][0] + groupCnt[group[i]]) % MOD;
            multiplier.mat[1][0] = (multiplier.mat[1][0] + find1[i][0]) % MOD;

            multiplier.mat[1][1] = (multiplier.mat[1][1] + n - groupCnt[group[i]] - res[i] + MOD)%MOD;
        }
        else{
            multiplier.mat[1][0] = (multiplier.mat[1][0] + res[i]) % MOD;

            multiplier.mat[0][1] = (multiplier.mat[0][1] + n) % MOD;
            multiplier.mat[1][1] = (multiplier.mat[1][1] + n - res[i]) % MOD;
        }
    }
    multiplier = mpow(multiplier, k-1);
    first = first * multiplier;
    ll Wsum = first.mat[0][0], Lsum = first.mat[0][1];
    ll ans = 0;
    if(canWin[1]){
        ans = (Wsum * n + groupCnt[group[1]] * Lsum + res[1] * Lsum) % MOD;
    }
    else ans = res[1] * Lsum % MOD;

    printf("%lld", ans);
}

Compilation message

startrek.cpp: In function 'int main()':
startrek.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     scanf("%lld %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
startrek.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2656 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2888 KB Output is correct
9 Correct 4 ms 2920 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 2 ms 2912 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2888 KB Output is correct
9 Correct 4 ms 2920 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 2 ms 2912 KB Output is correct
12 Correct 160 ms 26232 KB Output is correct
13 Correct 142 ms 30400 KB Output is correct
14 Execution timed out 1087 ms 16908 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2888 KB Output is correct
9 Correct 4 ms 2920 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 2 ms 2912 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 2 ms 2900 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2888 KB Output is correct
9 Correct 4 ms 2920 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 2 ms 2912 KB Output is correct
12 Correct 160 ms 26232 KB Output is correct
13 Correct 142 ms 30400 KB Output is correct
14 Execution timed out 1087 ms 16908 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -