oj.uz

Submission #588426

# Submission time Handle Problem Language Result Execution time Memory
588426 2022-07-03T09:19:29 Z 79brue Star Trek (CEOI20_startrek) C++17
30 / 100
 1000 ms 15376 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;
}

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

int group[400002], groupCnt[2];
int find1[400002][2];
int 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("%d %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]);
    }
    for(int i=1; i<=n; 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 + Lsum * groupCnt[group[1]] + Lsum * res[1]) % MOD;
    }
    else ans = Lsum * res[1] % 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("%d %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 2 ms 2644 KB Output is correct
2 Incorrect 17 ms 2776 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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2656 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2656 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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 25 ms 2824 KB Output is correct
8 Correct 38 ms 2892 KB Output is correct
9 Correct 21 ms 2900 KB Output is correct
10 Correct 18 ms 2772 KB Output is correct
11 Correct 27 ms 2780 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 25 ms 2824 KB Output is correct
8 Correct 38 ms 2892 KB Output is correct
9 Correct 21 ms 2900 KB Output is correct
10 Correct 18 ms 2772 KB Output is correct
11 Correct 27 ms 2780 KB Output is correct
12 Execution timed out 1079 ms 15376 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 25 ms 2824 KB Output is correct
8 Correct 38 ms 2892 KB Output is correct
9 Correct 21 ms 2900 KB Output is correct
10 Correct 18 ms 2772 KB Output is correct
11 Correct 27 ms 2780 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 16 ms 2772 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 25 ms 2824 KB Output is correct
8 Correct 38 ms 2892 KB Output is correct
9 Correct 21 ms 2900 KB Output is correct
10 Correct 18 ms 2772 KB Output is correct
11 Correct 27 ms 2780 KB Output is correct
12 Execution timed out 1079 ms 15376 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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