oj.uz

Submission #44285

# Submission time Handle Problem Language Result Execution time Memory
44285 2018-03-31T08:58:00 Z Nnandi Uzastopni (COCI15_uzastopni) C++14
0 / 160
 2 ms 464 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn=10005;
const int maxv=105;
vector<int> graf[maxn];

vector<bool> dp[maxn][maxv];
int v[maxn];

void bejar(int start, int apa, set<int> volt) {
    int ez=v[start];
    if(volt.count(ez)) {
        return;
    }
    volt.insert(ez);
    dp[start][ez][ez+1]=true;
    vector<int> dag[maxv];
    dag[ez].push_back(ez+1);
    for(int s:graf[start]) {
        bejar(s,start,volt);
        for(int i=0;i<maxv;i++) {
            for(int j=i+1;j<maxv;j++) {
                if(dp[s][i][j]) {
                    dag[i].push_back(j);
                }
            }
        }
    }
    vector<int> sor;
    bool volte[maxv];
    for(int i=0;i<=ez;i++) {
        sor.resize(0);
        memset(volte,false,maxv);
        sor.push_back(i);
        int it=0;
        while(it<(int)(sor.size())) {
            int akt=sor[it]; it++;
            volte[akt]=true;
            for(int s:dag[akt]) {
                if(!volte[s]) {
                    volte[s]=true;
                    sor.push_back(s);
                }
            }
        }
        for(int d:sor) {
            if(d>ez) {
                dp[start][i][d]=true;
            }
        }
    }
    volt.erase(ez);
    return;
}

void init(int n) {
    for(int i=0;i<n;i++) {
        for(int j=0;j<maxv;j++) {
            dp[i][j].resize(maxv);
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    init(n);
    for(int i=0;i<n;i++) {
        cin>>v[i];
    }
    for(int i=0;i<n-1;i++) {
        int u, v;
        cin>>u>>v;
        u--; v--;
        graf[u].push_back(v);
    }
    set<int> s;
    bejar(0,0,s);
    int sol=0;
    for(int i=0;i<=v[0];i++) {
        for(int j=v[0]+1;j<maxv;j++) {
            if(dp[0][i][j]) {
                sol++;
            }
        }
    }
    cout<<sol<<endl;
    return 0;
}

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 2 ms 276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1 ms 328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 1 ms 328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 1 ms 328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 1 ms 328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 2 ms 356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 1 ms 356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 1 ms 372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 1 ms 388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 2 ms 400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 2 ms 400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 1 ms 464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 1 ms 464 KB Execution killed with signal 11 (could be triggered by violating memory limits)