oj.uz

Submission #955000

# Submission time Handle Problem Language Result Execution time Memory
955000 2024-03-29T06:38:10 Z browntoad Nestabilnost (COI23_nestabilnost) C++14
12 / 100
 1500 ms 29260 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const double PI=acos(-1);
const ll maxn = 3e5+5;
const int inf = 1<<30;

int n;
vector<int> a(maxn), f(maxn), sf(maxn);
vector<int> aa(maxn), dp(maxn);
vector<int> g[maxn];
signed main(){
    IOS();
    cin>>n;
    REP1(i, n) cin>>a[i];
    REP(i, n) cin>>f[i];
    REP(i, n-1){
        int u, v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }
    sf[n] = inf;
    RREP(i, n){
        sf[i] = min(f[i], sf[i+1]);
    }

    int cur = 1;
    REP1(i, n){
        aa[i] = cur;
        for (auto v:g[cur]){
            if (v != aa[i-1]){
                cur = v;
                break;
            }
        }
    }

    vector<int> va;
    va.pb(0);

    REP1(i, n){
        int A = a[aa[i]];
        va.pb(A);

        int md = -1;
        dp[i] = dp[i-1] + sf[A];

        for (int j = i-1; j >= 1; j--){ // if i take j~i
            if (va[j+1] == 0){
                if (md == -1){
                    if (va[j] < va[i]) break;
                    md = va[j];
                }
                else {
                    if (va[j] != md) break;
                }
                dp[i] = min(dp[i], dp[j-1] + f[md]);
            }
            else {
                if (va[j] != va[j+1]-1) break;
                if (md == -1) dp[i] = min(dp[i], dp[j-1]+sf[va[i]]);
                else dp[i] = min(dp[i], dp[j-1]+f[md]);
            }
        }

    }
    cout<<dp[n]<<endl;
}
/*
7
3 1 0 1 2 0 1
8 2 8 6 8 5 8
1 6
7 5
3 4
6 4
2 5
2 3


2 min thonk
19 min write
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19288 KB Output is correct
2 Correct 22 ms 19292 KB Output is correct
3 Correct 22 ms 19292 KB Output is correct
4 Correct 13 ms 19292 KB Output is correct
5 Correct 8 ms 19316 KB Output is correct
6 Correct 8 ms 19288 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1551 ms 29260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19288 KB Output is correct
2 Correct 22 ms 19292 KB Output is correct
3 Correct 22 ms 19292 KB Output is correct
4 Correct 13 ms 19292 KB Output is correct
5 Correct 8 ms 19316 KB Output is correct
6 Correct 8 ms 19288 KB Output is correct
7 Incorrect 6 ms 19036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19288 KB Output is correct
2 Correct 22 ms 19292 KB Output is correct
3 Correct 22 ms 19292 KB Output is correct
4 Correct 13 ms 19292 KB Output is correct
5 Correct 8 ms 19316 KB Output is correct
6 Correct 8 ms 19288 KB Output is correct
7 Execution timed out 1551 ms 29260 KB Time limit exceeded
8 Halted 0 ms 0 KB -