oj.uz

Submission #843404

# Submission time Handle Problem Language Result Execution time Memory
843404 2023-09-04T01:40:01 Z Cookie Closing Time (IOI23_closing) C++17
26 / 100
 680 ms 62032 KB 
#include<bits/stdc++.h>
#include<fstream>
#include<closing.h>
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 2e5 + 5, inf = 1e9;
int n, x, y;
ll k;
int mxres = 0;
vt<pll>adj[mxn + 1];
vt<ll>compdep;
ll dp[3005][6005], distx[mxn + 1], disty[mxn + 1];
int u[mxn + 1], v[mxn + 1], w[mxn + 1];
bool path[mxn + 1];
int pa[3005];
void dfs(int s, int pre, ll dep, int root){
    if(root == x)distx[s] = dep;
    else disty[s] = dep;
    pa[s] = pre;
    for(auto [v, w]: adj[s]){
        if(v != pre){
            dfs(v, s, dep + w, root);
        }
    }
}
void ckmin(ll &a, ll b){
    a = min(a, b);
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
   
    n = N; x = ++X; y = ++Y; k = K;
    for(int i = 1; i <= n; i++){
        adj[i].clear(); path[i] = 0;
    }
    bool ok = 1;
    for(int i = 0; i < n - 1; i++){
 
        u[i] = ++U[i]; v[i] = ++V[i]; w[i] = W[i];
        
        adj[u[i]].pb(make_pair(v[i], w[i])); adj[v[i]].pb(make_pair(u[i], w[i]));
    }
    dfs(x, -1, 0, x); dfs(y, -1, 0, y);
    vt<ll>comp;
    for(int i = 1; i <= n; i++)comp.pb(min(distx[i], disty[i]));
    sort(comp.begin(), comp.end());
    ll curr = 0;
    int ans = 0;
    for(int i = 0; i < sz(comp); i++){
        if(curr + comp[i] <= k){
            curr += comp[i]; ans++;
        }
    }
    if(n <= 3000){
    
    int node = x;
    do{
        path[node] = 1;
        
        node = pa[node];
    }while(node != y);
    path[y] = 1;
    for(int j = 0; j <= n; j++){
        for(int l = 0; l <= 2 * n; l++){
            dp[j][l] = inf;
        }
    }
    
    dp[0][0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= 2 * n; j++){
            if(dp[i][j] == inf)continue;
            if(path[i + 1]){
                ckmin(dp[i + 1][j + 1], dp[i][j] + min(distx[i + 1], disty[i + 1]));
                ckmin(dp[i + 1][j + 2], dp[i][j] + max(distx[i + 1], disty[i + 1]));
            }else{
                ckmin(dp[i + 1][j], dp[i][j]);
                ckmin(dp[i + 1][j + 1], dp[i][j] + min(distx[i + 1], disty[i + 1]));
                ckmin(dp[i + 1][j + 2], dp[i][j] + max(distx[i + 1], disty[i + 1]));
            }
        }
    }
    for(int i = 0; i <= 2 * n; i++){
        if(dp[n][i] <= k){
            ans = max(ans, i);
        }
    }
    
    }
    return(ans);
}
/*
int main()
{
 
    int Q;
    assert(1 == scanf("%d", &Q));
 
    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);
 
    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
 
        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);
 
    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }
 
    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);
 
    return 0;
}
*/
/*
1
5 0 3 6
0 1 1
1 2 1
2 3 1
3 4 100
*/

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:50:10: warning: unused variable 'ok' [-Wunused-variable]
   50 |     bool ok = 1;
      |          ^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 34032 KB Output is correct
2 Correct 126 ms 38856 KB Output is correct
3 Correct 680 ms 62032 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct
3 Correct 2 ms 14168 KB Output is correct
4 Correct 3 ms 14168 KB Output is correct
5 Correct 3 ms 14168 KB Output is correct
6 Correct 3 ms 14168 KB Output is correct
7 Correct 2 ms 14168 KB Output is correct
8 Correct 2 ms 14168 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct
3 Correct 2 ms 14168 KB Output is correct
4 Correct 3 ms 14168 KB Output is correct
5 Correct 3 ms 14168 KB Output is correct
6 Correct 3 ms 14168 KB Output is correct
7 Correct 2 ms 14168 KB Output is correct
8 Correct 2 ms 14168 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Incorrect 3 ms 16472 KB 1st lines differ - on the 1st token, expected: '173', found: '200'
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct
3 Correct 2 ms 14168 KB Output is correct
4 Correct 3 ms 14168 KB Output is correct
5 Correct 3 ms 14168 KB Output is correct
6 Correct 3 ms 14168 KB Output is correct
7 Correct 2 ms 14168 KB Output is correct
8 Correct 2 ms 14168 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Incorrect 3 ms 16472 KB 1st lines differ - on the 1st token, expected: '173', found: '200'
13 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 14168 KB Output is correct
4 Correct 2 ms 14168 KB Output is correct
5 Correct 3 ms 14168 KB Output is correct
6 Correct 3 ms 14168 KB Output is correct
7 Correct 2 ms 12120 KB Output is correct
8 Correct 2 ms 12124 KB Output is correct
9 Correct 2 ms 12120 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 3 ms 14424 KB Output is correct
12 Correct 2 ms 14428 KB Output is correct
13 Correct 3 ms 14168 KB Output is correct
14 Correct 3 ms 14428 KB Output is correct
15 Correct 2 ms 14424 KB Output is correct
16 Correct 2 ms 14172 KB Output is correct
17 Correct 3 ms 14424 KB Output is correct
18 Correct 3 ms 14424 KB Output is correct
19 Correct 3 ms 14172 KB Output is correct
20 Correct 3 ms 14172 KB Output is correct
21 Correct 3 ms 14424 KB Output is correct
22 Correct 3 ms 14168 KB Output is correct
23 Correct 2 ms 14168 KB Output is correct
24 Correct 3 ms 14168 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 14168 KB Output is correct
4 Correct 2 ms 14168 KB Output is correct
5 Correct 3 ms 14168 KB Output is correct
6 Correct 3 ms 14168 KB Output is correct
7 Correct 3 ms 14168 KB Output is correct
8 Correct 2 ms 14168 KB Output is correct
9 Correct 2 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 3 ms 14168 KB Output is correct
13 Incorrect 3 ms 16472 KB 1st lines differ - on the 1st token, expected: '173', found: '200'
14 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 14168 KB Output is correct
4 Correct 2 ms 14168 KB Output is correct
5 Correct 3 ms 14168 KB Output is correct
6 Correct 3 ms 14168 KB Output is correct
7 Correct 3 ms 14168 KB Output is correct
8 Correct 2 ms 14168 KB Output is correct
9 Correct 2 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 3 ms 14168 KB Output is correct
13 Incorrect 3 ms 16472 KB 1st lines differ - on the 1st token, expected: '173', found: '200'
14 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 14168 KB Output is correct
4 Correct 2 ms 14168 KB Output is correct
5 Correct 3 ms 14168 KB Output is correct
6 Correct 3 ms 14168 KB Output is correct
7 Correct 3 ms 14168 KB Output is correct
8 Correct 2 ms 14168 KB Output is correct
9 Correct 2 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 3 ms 14168 KB Output is correct
13 Incorrect 3 ms 16472 KB 1st lines differ - on the 1st token, expected: '173', found: '200'
14 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 14168 KB Output is correct
4 Correct 2 ms 14168 KB Output is correct
5 Correct 3 ms 14168 KB Output is correct
6 Correct 3 ms 14168 KB Output is correct
7 Correct 3 ms 14168 KB Output is correct
8 Correct 2 ms 14168 KB Output is correct
9 Correct 2 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 3 ms 14168 KB Output is correct
13 Incorrect 3 ms 16472 KB 1st lines differ - on the 1st token, expected: '173', found: '200'
14 Halted 0 ms 0 KB -