Submission #979823

#	Time	Username	Problem	Language	Result	Execution time	Memory
979823		Requiem	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	97 ms	18004 KiB

uzastopni

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "uzastopni"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;

const int MAXN = 1e4 + 9;
int n, a[MAXN];

vector<int> g[MAXN];
ii edge[MAXN];

namespace subtask1{
    bool checkSubtask1(){
         return n <= 100;
    }

    int sz[102], mx;
    bool dp[102][102][102];
    bool reachable[102][102][102];

    void dfs(int u, int p){
         for(auto id: g[u]){
             int v = edge[id].se + edge[id].fi - u;
             if (v == p) continue;
             dfs(v, u);
             for(int j = 1; j <= mx; j++){
                 for(int k = j; k <= mx; k++){
                     if (dp[v][j][k] and j <= a[v] and a[v] <= k) {
                         reachable[u][j][k] = true;
                     }
                 }
             }
         }

//         if (u == 1){
//             for(int l = 1; l <= mx; l++){
//                 for(int r = l; r <= mx; r++){
//                     if (reachable[u][l][r]) cout << u << ' ' << l << ' ' << r << endl;
//                 }
//             }
//         }



         for(int i = mx; i >= 1; i--){
             if (i == a[u]){
                 dp[u][a[u]][a[u]] = true;
                 for(int j = i + 1; j <= mx; j++){
                     if (dp[u][a[u] + 1][j]) dp[u][i][j] = true;
                 }
             }
             if (i > a[u]){
                 for(int j = i; j <= mx; j++){
                     if (reachable[u][i][j]) {
                         dp[u][i][j] = true;
                         for(int k = j + 1; k <= mx; k++){
                             if (dp[u][j + 1][k]) {
                                 dp[u][i][k] = true;
                             }
                         }
                     }
                 }
             }

             if (i < a[u]){
                 for(int j = i; j < a[u]; j++){
                     if (reachable[u][i][j]){
                         for(int k = j + 1; k <= mx; k++){
                             if (dp[u][j + 1][k]) dp[u][i][k] = true;
                         }
                     }
                 }
             }
         }
    }
    void solveSubtask1(){
         memset(dp, false, sizeof(dp));
         memset(reachable, false, sizeof(reachable));
         for(int i = 1; i <= n; i++){
             maximize(mx, a[i]);
         }

         dfs(1, -1);

//         for(int i = 1; i <= n; i++){
//             cout << "NODE: " << i << endl;
//             for(int j = 1; j <= mx; j++){
//                 for(int k = 1; k <= mx; k++){
//                     if (dp[i][j][k] and j <= a[i] and a[i] <= k) cout << j << ' ' << k << endl;
//                 }
//             }
//         }
         int ans = 0;
         for(int i = 1; i <= mx; i++){
             for(int j = i; j <= mx; j++){
                 if (dp[1][i][j] and i <= a[1] and a[1] <= j) ans++;
             }
         }

         cout << ans << endl;
    }
}

namespace subtask2{
    bool checkSubtask2(){
         return true;
    }

    int mx;
    bitset<102> dp[10004][102];
    bitset<102> reachable[102];

    void dfs(int u, int p){
         for(auto id: g[u]){
             int v = edge[id].se + edge[id].fi - u;
             if (v == p) continue;
             dfs(v, u);
         }

         for(int i = 1; i <= mx; i++){
             reachable[i].reset();
         }

         for(auto id: g[u]){
             int v = edge[id].se + edge[id].fi - u;
             if (v == p) continue;
             for(int j = 1; j <= mx; j++){
                 for(int k = j; k <= mx; k++){
                     if (dp[v][j][k] and j <= a[v] and a[v] <= k) {
                         reachable[j][k] = true;
                     }
                 }
             }
         }




         for(int i = mx; i >= 1; i--){
             if (i == a[u]){
                 dp[u][a[u]][a[u]] = true;
                 dp[u][a[u]] |= dp[u][a[u] + 1];
             }
             if (i > a[u]){
                 for(int j = i; j <= mx; j++){
                     if (reachable[i][j]) {
                         dp[u][i][j] = true;
                         dp[u][i] |= dp[u][j + 1];
                     }
                 }
             }

             if (i < a[u]){
                 for(int j = i; j < a[u]; j++){
                     if (reachable[i][j]){
                         dp[u][i] |= dp[u][j + 1];
                     }
                 }
             }
         }
    }
    void solveSubtask2(){
         for(int i = 1; i <= n; i++){
             maximize(mx, a[i]);
         }

         dfs(1, -1);

//         for(int i = 1; i <= n; i++){
//             cout << "NODE: " << i << endl;
//             for(int j = 1; j <= mx; j++){
//                 for(int k = 1; k <= mx; k++){
//                     if (dp[i][j][k] and j <= a[i] and a[i] <= k) cout << j << ' ' << k << endl;
//                 }
//             }
//         }
         int ans = 0;
         for(int i = 1; i <= mx; i++){
             for(int j = i; j <= mx; j++){
                 if (dp[1][i][j] and i <= a[1] and a[1] <= j) ans++;
             }
         }

         cout << ans << endl;
    }
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n;
    FOR(i, 1, n){
        cin >> a[i];
    }

    FOR(i, 1, n - 1){
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v};
        g[u].pb(i);
        g[v].pb(i);
    }

    if (subtask1::checkSubtask1()) return subtask1::solveSubtask1(), 0;
    if (subtask2::checkSubtask2()) return subtask2::solveSubtask2(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message (stderr)

uzastopni.cpp:203:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  203 | main()
      | ^~~~
uzastopni.cpp: In function 'int main()':
uzastopni.cpp:207:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:208:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160