Submission #347437

#TimeUsernameProblemLanguageResultExecution timeMemory
347437shrek12357Uzastopni (COCI15_uzastopni)C++14
72 / 160
183 ms26092 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...