oj.uz

Submission #219895

# Submission time Handle Problem Language Result Execution time Memory
219895 2020-04-06T16:31:17 Z Haunted_Cpp Uzastopni (COCI15_uzastopni) C++17
80 / 160
 500 ms 18048 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 = 1e4 + 1;
const int V = 1e2 + 1;
 
vvi g (N); 
 
// We are dealing with sets. No duplicates allowed. This is why a bitset is allowed.
bitset<V> dp [N][V];
 
int joke [N];
bitset<V> Get [V];
 
void dfs (int node = 0) {
  GO (to, g[node]) {
    dfs (to);
  }
  dp[node][joke[node]][joke[node]] = 1;
  F0R (i, V) Get[i].reset();
  GO (to, g[node]) {
    FOR (x, 1, V) {
      FOR (y, x, V) {
        Get[x][y] = (Get[x][y] | dp[to][x][y]);
      }
    }
  }
  for (int tamanho = 1; tamanho < V; tamanho++) {
    for (int L = 1; L + tamanho < V; L++) {
      const int R = L + tamanho; // Inclusive
      for (int k = L; k < R; k++) {
        bool ansA = (dp[node][L][k] & Get[k + 1][R]);
        bool ansB = (Get[L][k] & dp[node][k + 1][R]);  
        dp[node][L][R] = (dp[node][L][R] | ansA);
        dp[node][L][R] = (dp[node][L][R] | ansB);
      }
    }
  } 
}
 
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;
  FOR (i, 1, V) res += dp[0][i].count();
  cout << res << '\n';
  return 0;
}

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16384 KB Output is correct
2 Correct 53 ms 16384 KB Output is correct
3 Correct 59 ms 16384 KB Output is correct
4 Correct 59 ms 16384 KB Output is correct
5 Correct 71 ms 16384 KB Output is correct
6 Correct 70 ms 16384 KB Output is correct
7 Correct 71 ms 16256 KB Output is correct
8 Correct 71 ms 16512 KB Output is correct
9 Correct 71 ms 16384 KB Output is correct
10 Correct 71 ms 16384 KB Output is correct
11 Execution timed out 1097 ms 16640 KB Time limit exceeded
12 Execution timed out 1097 ms 16640 KB Time limit exceeded
13 Execution timed out 1093 ms 16640 KB Time limit exceeded
14 Execution timed out 1097 ms 18048 KB Time limit exceeded
15 Execution timed out 1098 ms 18048 KB Time limit exceeded
16 Execution timed out 1093 ms 18048 KB Time limit exceeded
17 Execution timed out 1097 ms 16640 KB Time limit exceeded
18 Execution timed out 1095 ms 16640 KB Time limit exceeded
19 Execution timed out 1090 ms 16512 KB Time limit exceeded
20 Execution timed out 1098 ms 16512 KB Time limit exceeded