답안 #220003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220003 2020-04-06T19:56:52 Z Haunted_Cpp Uzastopni (COCI15_uzastopni) C++17
0 / 160
500 ms 16340 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};
 
// It should something like -> O ( N * V ^ 3 ), 50 pts  
 
const int N = 1e4 + 1;
const int V = 1e2 + 1;
 
vvi g (N); 
 
// We are dealing with sets. No duplicates allowed. This is why bitset is correct.
bitset<V> dp [N][V];
bitset<V> Get [V];

int joke [N];

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) {
      Get[x] = (Get[x] | dp[to][x]);
    }
  }
  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 / 2; 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);
        if (ansA || ansB) break;
      }
    }
  } 
}
 
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);
  }
  dfs ();
  int res = 0;
  FOR (i, 1, V) res += dp[0][i].count();
  cout << res << '\n';
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 640 KB Output isn't correct
2 Incorrect 16 ms 640 KB Output isn't correct
3 Incorrect 17 ms 768 KB Output isn't correct
4 Incorrect 17 ms 768 KB Output isn't correct
5 Incorrect 20 ms 768 KB Output isn't correct
6 Incorrect 20 ms 768 KB Output isn't correct
7 Incorrect 20 ms 768 KB Output isn't correct
8 Incorrect 20 ms 768 KB Output isn't correct
9 Incorrect 21 ms 768 KB Output isn't correct
10 Incorrect 21 ms 816 KB Output isn't correct
11 Execution timed out 1088 ms 16340 KB Time limit exceeded
12 Execution timed out 1095 ms 16176 KB Time limit exceeded
13 Execution timed out 1097 ms 16252 KB Time limit exceeded
14 Execution timed out 1095 ms 13352 KB Time limit exceeded
15 Execution timed out 1092 ms 13540 KB Time limit exceeded
16 Execution timed out 1098 ms 13560 KB Time limit exceeded
17 Execution timed out 1100 ms 16248 KB Time limit exceeded
18 Execution timed out 1098 ms 16248 KB Time limit exceeded
19 Execution timed out 1091 ms 11960 KB Time limit exceeded
20 Execution timed out 1098 ms 11608 KB Time limit exceeded