oj.uz

Submission #1064470

# Submission time Handle Problem Language Result Execution time Memory
1064470 2024-08-18T13:07:03 Z amirhoseinfar1385 Closing Time (IOI23_closing) C++17
18 / 100
 45 ms 19316 KB 
#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=3000+10;
struct yal{
    long long u,v,w;
    long long getad(long long fu){
        return (u^v^fu);
    }
}alle[maxn];
long long n,x,y,k,dp1[maxn][maxn],inf=1e18+1,dp2[maxn][maxn],dp[maxn][maxn];
vector<long long>adj[maxn];
vector<pair<long long,long long>>all;
long long inp[maxn];
vector<long long>ezaf;

void clear(){
    all.clear();
    for(long long i=0;i<=n+1;i++){
        inp[i]=0;
        adj[i].clear();
        for(long long j=0;j<=n+1;j++){
            dp1[i][j]=dp2[i][j]=dp[i][j]=inf;
        }
    }
}
void dfsdp(long long u,long long par=-1){
    if(par==-1){
        ezaf.push_back(0);
    }else{
        ezaf.push_back(all[u].first);
    }
    for(auto x:adj[u]){
        long long v=alle[x].getad(u);
        if(v!=par&&inp[v]==0){
            dfsdp(v,u);
        }
    }
}

void boro(long long u){
    dfsdp(u);
    sort(ezaf.begin(),ezaf.end());
    for(long long i=1;i<=(long long)ezaf.size();i++){
        dp[u][i]=dp[u][i-1]+ezaf[i-1];
    }
    for(long long i=(long long)ezaf.size()+1;i<=n+1;i++){
        dp[u][i]=inf;
    }
    ezaf.clear();
}


long long findpath(long long u,long long had,long long par=-1){
    long long ret=0;
    if(had==u){
        ret=1;
        inp[u]=1;
        return 1;
    }
    for(auto x:adj[u]){
        long long v=alle[x].getad(u);
        if(v!=par){
            ret|=findpath(v,had,u);
        }
    }
    if(ret){
        inp[u]=1;
    }
    return ret;
}

void dfs(long long u,long long vas,long long mas=0,long long par=-1){
    if(vas==0){
        all[u].first=mas;
    }else{
        all[u].second=mas;
    }
    for(auto x:adj[u]){
        long long v=alle[x].getad(u);
        if(v!=par){
            dfs(v,vas,mas+alle[x].w,u);
        }
    }
}

void calall(){
    dfs(x,0);
    dfs(y,1);
    for(long long i=0;i<n;i++){
        if(all[i].second<all[i].first){
            swap(all[i].first,all[i].second);
        }
    }
}

long long calres(){
    vector<long long>hey;
    for(long long i=0;i<n;i++){
        hey.push_back(all[i].first);
    }
    sort(hey.begin(),hey.end());
    long long ret=0,unnow=0;
    for(long long i=0;i<n;i++){
        if(hey[i]+unnow<=k){
            unnow+=hey[i];
            ret++;
        }else{
            break;
        }
    }
    vector<pair<long long,long long>>wtf;
    long long cnt=0;
    set<pair<long long,long long>>st;
    vector<long long>last(n+1),tof(n+1);
    for(long long i=0;i<n;i++){
        if(inp[i]){
            k-=all[i].first;
            cnt++;
            last[i]=2;
            wtf.push_back(make_pair(all[i].second-all[i].first,i));
        }
    }
    if(k<0){
        return ret;
    }
    sort(wtf.rbegin(),wtf.rend());
    vector<pair<long long,long long>>allv;
    for(long long i=0;i<(long long)wtf.size();i++){
        for(long long j=1;j<=n;j++){
            if(dp[wtf[i].second][j]>=inf){
                break;
            }
            allv.push_back(make_pair(dp[wtf[i].second][j]-dp[wtf[i].second][j-1],dp[wtf[i].second][j]-dp[wtf[i].second][j-1]+wtf[i].first));
        }
    } 
    for(long long i=0;i<=n+1;i++){
        for(long long j=0;j<=n+1;j++){
            dp2[i][j]=dp1[i][j]=inf;
        }
    }
    dp1[0][0]=dp2[(long long)allv.size()+1][0]=0;
    for(long long i=1;i<=(long long)allv.size();i++){
       // cout<<allv[i-1].first<<" "<<allv[i-1].second<<endl;
        for(long long j=0;j<=i;j++){
            dp1[i][j]=dp1[i-1][j];
            if(j>0){
                dp1[i][j]=min(dp1[i][j],dp1[i-1][j-1]+allv[i-1].first);
            }
        }
    }
    for(long long i=(long long)allv.size();i>=1;i--){
        for(long long j=0;j<=n;j++){
            dp2[i][j]=dp2[i+1][j];
            if(j>0){
                dp2[i][j]=min(dp2[i][j],dp2[i+1][j-1]+allv[i-1].second);
            }
        }
    }
    for(long long i=0;i<=n;i++){
        for(long long j=0;j<=n;j++){
            for(long long h=0;h<=n;h++){
                if(dp1[i][j]+dp2[i+1][h]>k){
                    continue;
                }else{
                    ret=max(ret,j+h*2);
                }
            }
        }
    }
    return ret;
}

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(long long i=0;i<n-1;i++){
        alle[i].u=U[i];
        alle[i].v=V[i];
        alle[i].w=W[i];
        adj[alle[i].u].push_back(i);
        adj[alle[i].v].push_back(i);
    }
    all.resize(n);
    calall();
    findpath(x,y);
    for(long long i=0;i<n;i++){
        if(inp[i]){
            boro(i);
        }
    }
    long long ret=calres();
    clear();
    return ret;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 19316 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1368 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 0 ms 1116 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1368 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 0 ms 1116 KB Output is correct
12 Correct 2 ms 1884 KB Output is correct
13 Correct 2 ms 1884 KB Output is correct
14 Correct 2 ms 1628 KB Output is correct
15 Correct 1 ms 1884 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Incorrect 1 ms 604 KB 2nd lines differ - on the 1st token, expected: '25', found: '18'
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1368 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 0 ms 1116 KB Output is correct
12 Correct 2 ms 1884 KB Output is correct
13 Correct 2 ms 1884 KB Output is correct
14 Correct 2 ms 1628 KB Output is correct
15 Correct 1 ms 1884 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Incorrect 1 ms 604 KB 2nd lines differ - on the 1st token, expected: '25', found: '18'
19 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 0 ms 1116 KB Output is correct
13 Correct 2 ms 1884 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 2 ms 1628 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 1 ms 1884 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 0 ms 604 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 0 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 0 ms 604 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 0 ms 604 KB Output is correct
37 Incorrect 1 ms 604 KB 2nd lines differ - on the 1st token, expected: '19', found: '10'
38 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 0 ms 1116 KB Output is correct
13 Correct 2 ms 1884 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 2 ms 1628 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 1 ms 1884 KB Output is correct
19 Incorrect 1 ms 604 KB 2nd lines differ - on the 1st token, expected: '25', found: '18'
20 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 0 ms 1116 KB Output is correct
13 Correct 2 ms 1884 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 2 ms 1628 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 1 ms 1884 KB Output is correct
19 Incorrect 1 ms 604 KB 2nd lines differ - on the 1st token, expected: '25', found: '18'
20 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 0 ms 1116 KB Output is correct
13 Correct 2 ms 1884 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 2 ms 1628 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 1 ms 1884 KB Output is correct
19 Incorrect 1 ms 604 KB 2nd lines differ - on the 1st token, expected: '25', found: '18'
20 Halted 0 ms 0 KB -