oj.uz

Submission #39436

# Submission time Handle Problem Language Result Execution time Memory
39436 2018-01-15T07:40:39 Z adamczh1 Uzastopni (COCI15_uzastopni) C++14
0 / 160
 0 ms 1840 KB 
#include <bits/stdc++.h>
using namespace std;

#define SIZE(x) (int)(x).size()

inline int readi(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int N;
int V[10001];
vector<int> adj[10001];
bitset<101> bs[10001][101]; // possible L for each R
vector<int> s[10001][101];

void dfs(int cur){
	for(int v:adj[cur]){
		dfs(v);
	}
	for(int i=1;i<=100;i++){
		if(i==V[cur]) bs[cur][i].set(i), bs[cur][i]|=bs[cur][i-1];
		for(int v:adj[cur])
			for(int j:s[v][i]){
				bs[cur][i].set(j);
				bs[cur][i]|=bs[cur][j-1];
			}
		for(int j=1;j<=i;j++)
			if(bs[cur][i][j] && V[cur]>=j && V[cur]<=i)
				s[cur][i].push_back(j);
	}
}

int main(){
	N=readi();
	for(int i=1; i<=N; i++){
		V[i]=readi();
	}
	for(int i=1; i<N; i++){
		int A=readi(),B=readi();
		adj[A].push_back(B);
	}
	dfs(1);
	int ans=0;
	for(int r=V[1];r<=100;r++){
		ans+=SIZE(s[1][r]);
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)