oj.uz

답안 #1019127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019127 2024-07-10T13:53:37 Z Cookie Uzastopni (COCI15_uzastopni) C++14
8 / 160
 66 ms 28244 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){
    pre[s][v[s]][v[s]] = dp[v[s]][v[s]][s] = 1;
    for(auto i: adj[s]){
        if(i != p){
            dfs(i, s);
            for(int j = 2; j <= 100; j++){
                for(int k = 1; k + j - 1 <= 100; k++){
                    int l = k, r = k + j - 1;
                    for(int z = l; z < r; z++){
                        if((pre[l][z][s] || dp[l][z][i]) && (pre[z + 1][r][s] || dp[z + 1][r][i])){
                            dp[l][r][s] = 1;
                        }
                    }
                }
            }
            for(int j = 1; j <= 100; j++){
                for(int k = j; k <= 100; k++){
                    //if(dp[j][k][s])cout << "aa";
                    pre[j][k][s] = dp[j][k][s]; 
                }
            }
        }
    }
    for(int i = 1; i <= 100; i++){
        for(int j = i; j <= 100; j++){
            if(i > v[s] || j < v[s])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
8.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 13660 KB Output isn't correct
2 Correct 30 ms 13656 KB Output is correct
3 Incorrect 33 ms 13660 KB Output isn't correct
4 Incorrect 33 ms 13656 KB Output isn't correct
5 Incorrect 47 ms 13804 KB Output isn't correct
6 Incorrect 42 ms 13912 KB Output isn't correct
7 Incorrect 37 ms 13660 KB Output isn't correct
8 Incorrect 41 ms 13908 KB Output isn't correct
9 Incorrect 39 ms 13904 KB Output isn't correct
10 Incorrect 39 ms 13908 KB Output isn't correct
11 Runtime error 3 ms 1884 KB Execution killed with signal 11
12 Runtime error 3 ms 1884 KB Execution killed with signal 11
13 Runtime error 6 ms 2136 KB Execution killed with signal 11
14 Runtime error 6 ms 4444 KB Execution killed with signal 11
15 Runtime error 12 ms 4444 KB Execution killed with signal 11
16 Runtime error 7 ms 4444 KB Execution killed with signal 11
17 Runtime error 3 ms 1884 KB Execution killed with signal 11
18 Runtime error 3 ms 1884 KB Execution killed with signal 11
19 Runtime error 66 ms 28204 KB Execution killed with signal 11
20 Runtime error 58 ms 28244 KB Execution killed with signal 11