oj.uz

Submission #219847

# Submission time Handle Problem Language Result Execution time Memory
219847 2020-04-06T14:24:51 Z Haunted_Cpp Uzastopni (COCI15_uzastopni) C++17
56 / 160
 15 ms 9856 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <string>
#include <cstring>
#include <bitset>
#include <random>
#include <chrono>
#include <iomanip>
 
/*
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
*/
 
#define FOR(i, a, b) for(int i = a; i < (int) b; i++)
#define F0R(i, a) FOR (i, 0, a)
#define ROF(i, a, b) for(int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define rsz resize
#define eb emplace_back
#define pb push_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define f first
#define s second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;
 
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};

const int N = 1e2 + 5;
const int V = 1e2 + 5;

vvi g (N); 

int dp [N][V][V];
int joke [N];

void dfs (int node = 0) {
  vpii bridge;
  bridge.eb(joke[node], node);
  GO (to, g[node]) {
    dfs (to);
    bridge.eb(joke[to], to);
  }
  sort (all(bridge));
  int start = -1;
  F0R (i, sz(bridge)) {
    if (bridge[i] == make_pair(joke[node], node)) {
      start = i;
      break;
    }
  }
  const int cur = joke[node];
  dp[node][cur][cur] = 1;
  // See above
  FOR (element, start, sz(bridge)) {
    int to = bridge[element].second;
    F0R (x, V) {
      FOR (y, x, V) {
        if (!dp[node][x][y]) continue;
        const int left = x;
        const int right = y;
        FOR (i, right + 1, V) { 
          // Bridge with [Left, Right] + ADD
          dp[node][left][i] += dp[to][right + 1][i];
        }
        FOR (i, 1, left) {
          // Bridge with ADD + [Left, Right]
          dp[node][i][right] += dp[to][i][left - 1];
        } 
      }
    }
  }
  R0F (element, start - 1) {
    int to = bridge[element].second;
    F0R (x, V) {
      FOR (y, x, V) {
        if (!dp[node][x][y]) continue;
        const int left = x;
        const int right = y;
        FOR (i, right + 1, V) { 
          // Bridge with [Left, Right] + ADD
          dp[node][left][i] += dp[to][right + 1][i];
        }
        FOR (i, 1, left) {
          // Bridge with ADD + [Left, Right]
          dp[node][i][right] += dp[to][i][left - 1];
        } 
      }
    }
  } 
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  F0R (i, n) cin >> joke[i];
  F0R (i, n - 1) {
    int st, et;
    cin >> st >> et;
    --st; --et;
    g[st].eb(et);
  }
  memset (dp, 0, sizeof(dp));
  dfs ();
  int res = 0;
  F0R (i, V) F0R (j, V) {
    res += dp[0][i][j];
  }
  cout << res << '\n';
  return 0;
}

Subtask #1
56.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4864 KB Output is correct
2 Correct 8 ms 4864 KB Output is correct
3 Incorrect 8 ms 4864 KB Output isn't correct
4 Incorrect 8 ms 4864 KB Output isn't correct
5 Incorrect 8 ms 4864 KB Output isn't correct
6 Correct 8 ms 4864 KB Output is correct
7 Correct 9 ms 4864 KB Output is correct
8 Correct 9 ms 4864 KB Output is correct
9 Correct 8 ms 4864 KB Output is correct
10 Correct 8 ms 4864 KB Output is correct
11 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 15 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 15 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)