oj.uz

답안 #675223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
675223 2022-12-27T03:11:44 Z Do_you_copy Uzastopni (COCI15_uzastopni) C++17
136 / 160
 101 ms 35316 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e4 + 10;
const int maxM = 1e2 + 10;
const int Mod = 1e9 + 7;
//const int inf =
int n;

bitset <maxM> dp[maxN][maxM];
vector <int> adj[maxN];
int a[maxN];
void dfs(int u){
    bitset <maxM> B[maxM];
    dp[u][a[u]][a[u]] = 1;
    for (int i: adj[u]){
        dfs(i);
    }
    for (int i: adj[u]){
        for (int j = 1; j <= 100; ++j){
            B[j] |= dp[i][j];
        }
    }
    for (int i = 1; i <= 100; ++i){
        for (int j = i + 1; j <= 100; ++j){
            if (B[i][j - 1]) B[i] |= B[j];
        }
    }
    for (int i = 1; i <= a[u]; ++i){
        for (int j = a[u]; j <= 100; ++j){
            if ((i == a[u] || B[i][a[u] - 1]) && (j == a[u] || B[a[u] + 1][j])) dp[u][i][j] = 1;
        }
    }
}

void Init(){
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
    }
    dfs(1);
    int ans = 0;
    for (int i = 1; i <= 100; ++i){
        ans += dp[1][i].count();
    }
    cout << ans << "\n";
}

#define debu
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
136.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 75 ms 17928 KB Output is correct
12 Correct 72 ms 17920 KB Output is correct
13 Correct 71 ms 17996 KB Output is correct
14 Runtime error 101 ms 35280 KB Memory limit exceeded
15 Runtime error 98 ms 35260 KB Memory limit exceeded
16 Runtime error 98 ms 35316 KB Memory limit exceeded
17 Correct 73 ms 17900 KB Output is correct
18 Correct 75 ms 17916 KB Output is correct
19 Correct 88 ms 17868 KB Output is correct
20 Correct 85 ms 17812 KB Output is correct