oj.uz

Submission #585702

# Submission time Handle Problem Language Result Execution time Memory
585702 2022-06-29T08:44:43 Z 반딧불(#8385) Star Trek (CEOI20_startrek) C++17
23 / 100
 1000 ms 12772 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[100002];
int depth[100002];
int DP[100002];
int DProot[100002];
ll ans;

void dfs(int x, int p=-1){
    for(auto y: link[x]){
        if(y==p) continue;
        depth[y] = depth[x] + 1;
        dfs(y, x);
        if(!DP[y]) DP[x] = 1;
    }
}

void dfs2(int x, int p=-1, bool winUp = 0){
    DProot[x] = (DP[x] || winUp);
    int cnt = 0;
    for(auto y: link[x]) if(y!=p) cnt += !DP[y];
    for(auto y: link[x]){
        if(y==p) continue;
        dfs2(y, x, !winUp && !(cnt-!DP[y]));
    }
}

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

int dfsFind2(int x, int p=-1){
    if(depth[x] % 2 == 0){ /// my turn
        int ret = 1;
        for(auto y: link[x]){
            if(y==p) continue;
            ret += dfsFind2(y, x);
        }
        return ret;
    }
    else{ /// your turn
        int cnt = 0;
        for(auto y: link[x]){
            if(y!=p && !DP[y]) cnt++;
        }
        if(cnt > 1) return 0;
        assert(cnt == 1);
        for(auto y: link[x]){
            if(y!=p && !DP[y]) return dfsFind2(y, x);
        }
        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);
    }
//    dfs(1);
//    dfs2(1);
    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]);

    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", ans%MOD);
}

Compilation message

startrek.cpp: In function 'int main()':
startrek.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
startrek.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         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 16 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 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 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 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 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 18 ms 2748 KB Output is correct
8 Correct 21 ms 2784 KB Output is correct
9 Correct 14 ms 2704 KB Output is correct
10 Correct 14 ms 2644 KB Output is correct
11 Correct 15 ms 2644 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 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 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 18 ms 2748 KB Output is correct
8 Correct 21 ms 2784 KB Output is correct
9 Correct 14 ms 2704 KB Output is correct
10 Correct 14 ms 2644 KB Output is correct
11 Correct 15 ms 2644 KB Output is correct
12 Execution timed out 1074 ms 12772 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 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 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 18 ms 2748 KB Output is correct
8 Correct 21 ms 2784 KB Output is correct
9 Correct 14 ms 2704 KB Output is correct
10 Correct 14 ms 2644 KB Output is correct
11 Correct 15 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 14 ms 2644 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 2644 KB Output is correct
2 Correct 1 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 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 18 ms 2748 KB Output is correct
8 Correct 21 ms 2784 KB Output is correct
9 Correct 14 ms 2704 KB Output is correct
10 Correct 14 ms 2644 KB Output is correct
11 Correct 15 ms 2644 KB Output is correct
12 Execution timed out 1074 ms 12772 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 16 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -