oj.uz

Submission #347437

# Submission time Handle Problem Language Result Execution time Memory
347437 2021-01-13T04:16:49 Z shrek12357 Uzastopni (COCI15_uzastopni) C++14
72 / 160
 183 ms 26092 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <iomanip>
#include <bitset>
//#include "molecules.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0);

const int MAXN = 105;
const int MAXV = 1005;

int dp[MAXV][MAXN][MAXN];
vector<int> nums;
vector<int> adjList[MAXV];
int n;

void dfs(int src) {
	bool temp[MAXN][MAXN];
	bool cur[MAXN][MAXN];
	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++) {
			temp[i][j] = false;
			cur[i][j] = false;
		}
	}
	for (auto i : adjList[src]) {
		dfs(i);
	}
	temp[nums[src]][nums[src]] = true;
	for (auto i : adjList[src]) {
		for (int j = 0; j < MAXN; j++) {
			for (int k = j; k < MAXN; k++) {
				temp[j][k] |= dp[i][j][k];
			}
		}
	}
	for (int i = 0; i < MAXN; i++) {
		for (int j = i; j < MAXN; j++) {
			for (int k = i; k <= j; k++) {
				if (i == j) {
					cur[i][j] |= temp[i][j];
				}
				else if (k == j) {
					cur[i][j] |= temp[i][j];
				}
				else if (temp[i][k] && temp[k + 1][j]) {
					cur[i][j] |= true;
				}
			}
		}
	}
	for (int i = 0; i < MAXN; i++) {
		for (int j = i; j < MAXN; j++) {
			if (i < nums[src] && nums[src] < j) {
				dp[src][i][j] = (cur[i][nums[src] - 1] && cur[nums[src] + 1][j]);
			}
			if (i == nums[src] && j == nums[src]) {
				dp[src][i][j] = true;
			}
			else if (i == nums[src]) {
				dp[src][i][j] = cur[i + 1][j];
			}
			else if (j == nums[src]) {
				dp[src][i][j] = cur[i][j - 1];
			}
		}
	}
}

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		temp--;
		nums.push_back(temp);
	}

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adjList[a].push_back(b);
	}
	dfs(0);
	int ans = 0;
	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++) {
			ans += dp[0][i][j];
		}
	}
	cout << ans << endl;
}

Subtask #1
72.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 876 KB Output is correct
2 Correct 22 ms 1004 KB Output is correct
3 Incorrect 27 ms 1004 KB Output isn't correct
4 Correct 25 ms 1004 KB Output is correct
5 Correct 32 ms 1260 KB Output is correct
6 Correct 32 ms 4332 KB Output is correct
7 Correct 32 ms 4332 KB Output is correct
8 Correct 32 ms 4332 KB Output is correct
9 Correct 31 ms 2412 KB Output is correct
10 Correct 33 ms 2556 KB Output is correct
11 Runtime error 10 ms 1132 KB Execution killed with signal 6 (could be triggered by violating memory limits)
12 Runtime error 7 ms 748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
13 Runtime error 8 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
14 Runtime error 8 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
15 Runtime error 8 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
16 Runtime error 9 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
17 Runtime error 8 ms 748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
18 Runtime error 8 ms 748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
19 Runtime error 183 ms 26092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 149 ms 20844 KB Execution killed with signal 11 (could be triggered by violating memory limits)