oj.uz

답안 #347430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347430 2021-01-13T04:03:05 Z shrek12357 Uzastopni (COCI15_uzastopni) C++14
72 / 160
 34 ms 4332 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;

int dp[MAXN][MAXN][MAXN];
vector<int> nums;
vector<int> adjList[MAXN];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 876 KB Output is correct
2 Correct 23 ms 1004 KB Output is correct
3 Incorrect 25 ms 1004 KB Output isn't correct
4 Correct 27 ms 1004 KB Output is correct
5 Correct 30 ms 1132 KB Output is correct
6 Correct 33 ms 4332 KB Output is correct
7 Correct 32 ms 4332 KB Output is correct
8 Correct 34 ms 4332 KB Output is correct
9 Correct 32 ms 2412 KB Output is correct
10 Correct 32 ms 2412 KB Output is correct
11 Runtime error 5 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
12 Runtime error 5 ms 896 KB Execution killed with signal 6 (could be triggered by violating memory limits)
13 Runtime error 5 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
14 Runtime error 5 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
15 Runtime error 5 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
16 Runtime error 5 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
17 Runtime error 5 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
18 Runtime error 5 ms 876 KB Execution killed with signal 6 (could be triggered by violating memory limits)
19 Runtime error 10 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 11 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)