oj.uz

Submission #585733

# Submission time Handle Problem Language Result Execution time Memory
585733 2022-06-29T09:19:52 Z 반딧불(#8385) Star Trek (CEOI20_startrek) C++17
23 / 100
 1000 ms 4360 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

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;
}

int n;
ll k;
vector<int> link[1002];
int mat[1002][1002];
int depth[1002];
ll group[1002], groupCnt[2];
ll ans;

ll DP[2][1002];
ll find1[1002], find2[1002];

void dfs(int x, int p, int r){
    if(r==1){
        group[x] = depth[x]%2;
        groupCnt[group[x]]++;
    }
    for(auto y: link[x]){
        if(y==p) continue;
        depth[y] = depth[x] + 1;
        dfs(y, x, r);
        if(!mat[r][y]) mat[r][x] = 1;
    }
}

int dfsFind(int x, int p, int dp, int r){ /// ������ ������ �ϴ� ��� ���� �� ���� ã��
    if(dp % 2 == 0){ /// my turn
        int cnt = 0;
        for(auto y: link[x]){
            if(y!=p && !mat[r][y]) cnt++;
        }
        if(cnt > 1) return 0;
        assert(cnt == 1);
        for(auto y: link[x]){
            if(y!=p && !mat[r][y]) return dfsFind(y, x, dp+1, r);
        }
        exit(1);
    }
    else{ /// your turn
        int ret = 1;
        for(auto y: link[x]){
            if(y==p) continue;
            ret += dfsFind(y, x, dp+1, r);
        }
        return ret;
    }
}

int dfsFind2(int x, int p, int dp, int r){
    if(dp % 2 == 0){ /// my turn
        int ret = 1;
        for(auto y: link[x]){
            if(y==p) continue;
            ret += dfsFind2(y, x, dp+1, r);
        }
        return ret;
    }
    else{ /// your turn
        int cnt = 0;
        for(auto y: link[x]){
            if(y!=p && !mat[r][y]) cnt++;
        }
        if(cnt > 1) return 0;
        assert(cnt == 1);
        for(auto y: link[x]){
            if(y!=p && !mat[r][y]) return dfsFind2(y, x, dp+1, r);
        }
        exit(1);
    }
}

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(y);
        link[y].push_back(x);
    }
//    for(int i=n; i>=1; i--){
//        for(int x=0; x<=n+1; x++) depth[x] = DP[x] = 0;
//        dfs(i), DProot[i] = DP[i];
//    }
//    for(int i=1; i<=n; i++) printf("%d ", DProot[i]);

    for(int i=1; i<=n; i++){
        dfs(i, -1, i);
        if(mat[i][i]) find1[i] = groupCnt[!group[i]] - dfsFind(i, -1, 0, i);
        else find2[i] = dfsFind2(i, -1, 0, i);
        DP[0][i] = mat[i][i];
    }

    for(int turn=1; turn<=k; turn++){
        int b = turn%2;

        /// ��ó��
        ll Wsum = 0; /// �̱�� ������
        for(int i=1; i<=n; i++) Wsum = (Wsum + DP[!b][i]) % MOD;
        ll Lsum = mpow(n, 2*turn-1) - Wsum; /// ���� ������

        /// ���� ���
        for(int i=1; i<=n; i++){
            DP[b][i] = 0;
            if(mat[i][i]){ /// ���⼭ �����ϸ� �̱�� ���
                /// ? -> W
                DP[b][i] = (DP[b][i] + Wsum * n) % MOD;
                /// my turn -> L
                DP[b][i] = (DP[b][i] + groupCnt[group[i]] * Lsum) % MOD;
                /// your turn -> L
                DP[b][i] = (DP[b][i] + find1[i] * Lsum) % MOD;
            }
            else{
                DP[b][i] = (DP[b][i] + find2[i] * Lsum) % MOD;
            }
        }
    }

//    if(DP[1]){ /// ���������� �̱� ��
//        ll W = 0; /// ? -> W
//        for(int i=1; i<=n; i++) if(DProot[i]) W++;
//        ans += W*n;
//
//        ll myturn = 0; /// my turn -> L
//        for(int i=1; i<=n; i++) if(depth[i] % 2 == 0) myturn++;
//        ans += myturn * (n-W);
//
//        ll dw = 0;
//        for(int i=1; i<=n; i++) if(DP[i]) dw++;
//        ll tmp = n - myturn - dfsFind(1); /// your turn -> L
//        ans += tmp * (n-W);
//    }
//    else{ /// ���������� �� ��
//        ll L = 0;
//        for(int i=1; i<=n; i++) if(!DProot[i]) L++;
//        ans += L * dfsFind2(1);
//    }

    printf("%lld", DP[k%2][1]);
}

Compilation message

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

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 328 KB Output is correct
3 Execution timed out 1085 ms 340 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 22 ms 4300 KB Output is correct
8 Correct 28 ms 4300 KB Output is correct
9 Correct 16 ms 4264 KB Output is correct
10 Correct 18 ms 4360 KB Output is correct
11 Correct 21 ms 4240 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 22 ms 4300 KB Output is correct
8 Correct 28 ms 4300 KB Output is correct
9 Correct 16 ms 4264 KB Output is correct
10 Correct 18 ms 4360 KB Output is correct
11 Correct 21 ms 4240 KB Output is correct
12 Runtime error 1 ms 468 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 22 ms 4300 KB Output is correct
8 Correct 28 ms 4300 KB Output is correct
9 Correct 16 ms 4264 KB Output is correct
10 Correct 18 ms 4360 KB Output is correct
11 Correct 21 ms 4240 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 23 ms 4308 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 22 ms 4300 KB Output is correct
8 Correct 28 ms 4300 KB Output is correct
9 Correct 16 ms 4264 KB Output is correct
10 Correct 18 ms 4360 KB Output is correct
11 Correct 21 ms 4240 KB Output is correct
12 Runtime error 1 ms 468 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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