oj.uz

답안 #888607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888607 2023-12-18T01:29:23 Z fanwen Nestabilnost (COI23_nestabilnost) C++17
41 / 100
 194 ms 206648 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

const int MAX = 3e5 + 5;

int n, a[MAX], f[MAX];
vector <int> adj[MAX];

namespace sub1 {
    bool check() {
        return n <= 5000;
    }
    long long dp[5005][5005], ans[MAX];

    void dfs(int u, int p) {
        for (int i = a[u] + 1; i <= n; ++i) dp[u][i] = f[i];
        for (auto v : adj[u]) if(v != p) {
            dfs(v, u);
            for (int k = a[u] + 1; k <= n; ++k) {
                if(a[v] == (a[u] + 1) % k) {
                    dp[u][k] += min(ans[v], dp[v][k] - f[k]);
                } else {
                    dp[u][k] += ans[v];
                }
            }
        }
        ans[u] = *min_element(dp[u] + 1, dp[u] + n + 1);
    }
    void solve() {
        memset(dp, 0x3f, sizeof dp);
        dfs(1, 0);
        cout << ans[1]; exit(0);
    }
}

void you_make_it(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> f[i];

    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if(sub1::check()) sub1::solve();
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("nestabilnost");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

code1.cpp: In function 'int main()':
code1.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
code1.cpp:61:5: note: in expansion of macro 'file'
   61 |     file("nestabilnost");
      |     ^~~~
code1.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
code1.cpp:61:5: note: in expansion of macro 'file'
   61 |     file("nestabilnost");
      |     ^~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 206284 KB Output is correct
2 Correct 175 ms 206416 KB Output is correct
3 Correct 160 ms 206420 KB Output is correct
4 Correct 174 ms 206408 KB Output is correct
5 Correct 175 ms 206308 KB Output is correct
6 Correct 175 ms 206648 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 27988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 205396 KB Output is correct
2 Correct 24 ms 205580 KB Output is correct
3 Correct 24 ms 205660 KB Output is correct
4 Correct 27 ms 205392 KB Output is correct
5 Correct 24 ms 205400 KB Output is correct
6 Correct 23 ms 205396 KB Output is correct
7 Correct 24 ms 205392 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 206284 KB Output is correct
2 Correct 175 ms 206416 KB Output is correct
3 Correct 160 ms 206420 KB Output is correct
4 Correct 174 ms 206408 KB Output is correct
5 Correct 175 ms 206308 KB Output is correct
6 Correct 175 ms 206648 KB Output is correct
7 Correct 24 ms 205396 KB Output is correct
8 Correct 24 ms 205580 KB Output is correct
9 Correct 24 ms 205660 KB Output is correct
10 Correct 27 ms 205392 KB Output is correct
11 Correct 24 ms 205400 KB Output is correct
12 Correct 23 ms 205396 KB Output is correct
13 Correct 24 ms 205392 KB Output is correct
14 Correct 175 ms 205912 KB Output is correct
15 Correct 176 ms 205904 KB Output is correct
16 Correct 179 ms 205968 KB Output is correct
17 Correct 177 ms 205960 KB Output is correct
18 Correct 186 ms 206168 KB Output is correct
19 Correct 177 ms 205904 KB Output is correct
20 Correct 170 ms 205792 KB Output is correct
21 Correct 176 ms 205912 KB Output is correct
22 Correct 175 ms 205904 KB Output is correct
23 Correct 175 ms 205960 KB Output is correct
24 Correct 176 ms 206004 KB Output is correct
25 Correct 171 ms 205904 KB Output is correct
26 Correct 173 ms 205940 KB Output is correct
27 Correct 172 ms 206012 KB Output is correct

Subtask #5
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 206284 KB Output is correct
2 Correct 175 ms 206416 KB Output is correct
3 Correct 160 ms 206420 KB Output is correct
4 Correct 174 ms 206408 KB Output is correct
5 Correct 175 ms 206308 KB Output is correct
6 Correct 175 ms 206648 KB Output is correct
7 Incorrect 118 ms 27988 KB Output isn't correct
8 Halted 0 ms 0 KB -