oj.uz

답안 #1019101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019101 2024-07-10T13:33:50 Z Cookie Uzastopni (COCI15_uzastopni) C++14
0 / 160
 350 ms 15964 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 = 10000 + 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[105][105], pre[105][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 <= v[i]; j++){
                for(int k = v[i]; k <= 100; k++){
                    if(dp[j][k][i]){
                        dp[j][k][s] = 1;  
                        for(int l = k + 1; l <= 100; l++){
                            if(pre[k + 1][l][s])dp[j][l][s] = 1;
                        }
                        
                        for(int l = j - 1; l >= 1; l--){
                            if(pre[l][j - 1][s])dp[l][k][s] = 1;
                        }
                       
                    }
                }
            }
            for(int j = 1; j <= 100; j++){
                for(int k = j; k <= 100; k++){
                    pre[j][k][s] = dp[j][k][s]; 
                }
            }
        }
    }
    pre[v[s]][v[s] - 1][s] = pre[v[s] + 1][v[s]][s] = 1;
    for(int i = 1; i <= v[s]; i++){
        for(int j = v[s]; j <= 100; j++){
            if(i <= v[s] && j >= v[s] && pre[i][v[s] - 1][s] && pre[v[s] + 1][j][s]){
                dp[i][j][s] = 1;
            }else{
                dp[i][j][s] = 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[i][j][1];
        }
    }
    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
0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 8792 KB Output isn't correct
2 Incorrect 5 ms 8996 KB Output isn't correct
3 Incorrect 6 ms 8284 KB Output isn't correct
4 Incorrect 6 ms 7772 KB Output isn't correct
5 Incorrect 7 ms 8220 KB Output isn't correct
6 Incorrect 8 ms 13632 KB Output isn't correct
7 Incorrect 8 ms 13656 KB Output isn't correct
8 Incorrect 9 ms 13660 KB Output isn't correct
9 Incorrect 8 ms 13460 KB Output isn't correct
10 Incorrect 9 ms 13404 KB Output isn't correct
11 Incorrect 209 ms 9304 KB Output isn't correct
12 Incorrect 186 ms 8920 KB Output isn't correct
13 Incorrect 203 ms 8440 KB Output isn't correct
14 Incorrect 350 ms 15964 KB Output isn't correct
15 Incorrect 311 ms 15960 KB Output isn't correct
16 Incorrect 284 ms 15964 KB Output isn't correct
17 Incorrect 182 ms 8452 KB Output isn't correct
18 Incorrect 170 ms 8280 KB Output isn't correct
19 Incorrect 326 ms 14284 KB Output isn't correct
20 Incorrect 288 ms 14168 KB Output isn't correct