oj.uz

답안 #1019085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019085 2024-07-10T13:13:28 Z Cookie Uzastopni (COCI15_uzastopni) C++14
72 / 160
 271 ms 35828 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
const int cox[4] = {1, 0, -1, 0};
const int coy[4] = {0, -1, 0, 1};
const ll mod = 998244353, pr = 31;
const int mxn = 1e4 + 5, mxs = 3e5 * 50, sq = 500, mxv = 100 + 1;
const int max_iter = 8e4, global_iter = 15e5 + 5;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
bitset<mxv>dp[10005][105], pre[10005][105];
int v[mxn + 1];
vt<int>adj[mxn + 1];
void dfs(int s, int p){
    
    for(auto i: adj[s]){
        if(i != p){
            dfs(i, s);
            for(int j = 1; j <= 100; j++){
                for(int k = j; k <= 100; k++){
                    if(dp[i][j][k]){
                        dp[s][j][k] = 1;  
                        
                        for(int l = k + 1; l <= 100; l++){
                            if(pre[s][k + 1][l])dp[s][j][l] = 1;
                        }
                        
                        for(int l = j - 1; l >= 1; l--){
                            if(pre[s][l][j - 1])dp[s][l][k] = 1;
                        }
                       
                    }
                }
            }
            for(int j = 1; j <= 100; j++){
                for(int k = j; k <= 100; k++){
                    pre[s][j][k] = dp[s][j][k]; 
                }
            }
        }
    }

    pre[s][v[s]][v[s] - 1] = pre[s][v[s] + 1][v[s]] = 1;
    for(int i = 1; i <= 100; i++){
        for(int j = i; j <= 100; j++){
            if(i <= v[s] && j >= v[s] && pre[s][i][v[s] - 1] && pre[s][v[s] + 1][j]){
                dp[s][i][j] = 1;
            }else{
                dp[s][i][j] = 0;
            }
        }
    }
}
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> v[i];
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        adj[a].pb(b); adj[b].pb(a);
    }
    dfs(1, -1);
    int res = 0;
    for(int i = 1; i <= 100; i++){
        for(int j = i; j <= 100; j++){
           
            res += dp[1][i][j];
        }
    }
    cout << res;
}



signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("KHONG.inp", "r", stdin);
    //freopen("KHONG.out", "w", stdout);
    int tt; tt = 1;
    while(tt--)solve();
    return(0);
}

Subtask #1
72.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Incorrect 2 ms 860 KB Output isn't correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 3 ms 1036 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Runtime error 244 ms 33872 KB Memory limit exceeded
12 Runtime error 235 ms 33784 KB Memory limit exceeded
13 Runtime error 240 ms 33872 KB Memory limit exceeded
14 Runtime error 271 ms 35788 KB Memory limit exceeded
15 Runtime error 254 ms 35828 KB Memory limit exceeded
16 Runtime error 263 ms 35668 KB Memory limit exceeded
17 Runtime error 238 ms 33872 KB Memory limit exceeded
18 Runtime error 230 ms 33876 KB Memory limit exceeded
19 Runtime error 253 ms 33744 KB Memory limit exceeded
20 Runtime error 245 ms 33876 KB Memory limit exceeded