oj.uz

답안 #472080

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
472080 2021-09-12T20:19:08 Z SirCovidThe19th Uzastopni (COCI15_uzastopni) C++17
72 / 160
 500 ms 3004 KB 
#include <bits/stdc++.h>
using namespace std; 

#define FOR(i, x, y) for (int i = x; i < y; i++)

const int mx = 10005, mv = 12;

int n, A[mx], ans; vector<int> adj[mx]; bitset<mv> dp[mx][mv];

void dfs(int i){
    dp[i][A[i]][A[i]] = 1;
    for (int x : adj[i]){
        dfs(x); 
        FOR(j, 0, mv){
			if (j < A[i]) dp[i][j] |= dp[x][j] << (mv - A[i]) >> (mv - A[i]);
			if (j > A[i]) dp[i][j] |= dp[x][j];
		}
    }
    for (int j = mv - 1; j; j--) FOR(k, j, mv - 1)
        if (dp[i][j][k]) dp[i][j] |= dp[i][k + 1];
    FOR(j, 0, mv){
        if (j <= A[i]) dp[i][j] = dp[i][j] >> A[i] << A[i];
        else dp[i][j].reset();
    }
}
int main(){
    cin >> n;
    FOR(i, 0, n) cin >> A[i];
    FOR(i, 0, n - 1){
        int a, b; cin >> a >> b; 
        adj[a - 1].push_back(b - 1);
    }
    dfs(0);
    FOR(i, 0, mv) ans += dp[0][i].count();
    cout<<ans<<endl;
}

Subtask #1
72.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 536 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Incorrect 1 ms 460 KB Output isn't correct
7 Incorrect 1 ms 540 KB Output isn't correct
8 Incorrect 1 ms 460 KB Output isn't correct
9 Incorrect 1 ms 460 KB Output isn't correct
10 Incorrect 1 ms 460 KB Output isn't correct
11 Incorrect 11 ms 1740 KB Output isn't correct
12 Correct 11 ms 1744 KB Output is correct
13 Correct 12 ms 1692 KB Output is correct
14 Incorrect 11 ms 2656 KB Output isn't correct
15 Incorrect 11 ms 2636 KB Output isn't correct
16 Incorrect 11 ms 2636 KB Output isn't correct
17 Correct 11 ms 1740 KB Output is correct
18 Correct 11 ms 1684 KB Output is correct
19 Runtime error 11 ms 3004 KB Execution killed with signal 11
20 Execution timed out 1082 ms 1912 KB Time limit exceeded