oj.uz

Submission #848460

# Submission time Handle Problem Language Result Execution time Memory
848460 2023-09-12T17:43:23 Z oneloveforever Closing Time (IOI23_closing) C++17
43 / 100
 140 ms 44956 KB 
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
const long long  inf=1e18+7;
const int M=3007;
using Graph = vector<vector<pair<int, long long>>> ;
void dfs(int x,int par,Graph &edge,vector<long long>&dist)
{
    for(auto [node,value]:edge[x])
    {
        if(node==par)continue;
        dist[node]=dist[x]+value;
        dfs(node,x,edge,dist);
    }
}
int Sub1(int N,long long K,vector<ll>distX,vector<ll>distY)
{
    vector<ll>que;
    for(int i=1; i<=N; i++)
    {
        que.push_back(distX[i]);
        que.push_back(distY[i]);
    }
    sort(que.begin(),que.end());
    ll res=K;
    int ans=0;
    for(int value:que)
    {
        if(res<value)break;
        res-=value;
        ans++;
    }
    return ans;
}
bool checkLinear(int N,Graph edge,vector<int>&deg)
{
    int maxv=0;
    for(int i=1; i<=N; i++)
    {
        for(auto [x,w]:edge[i])deg[x]++;
        maxv=max(maxv,deg[i]);
    }
    return maxv<=2;
}
void bfs(int N,int need_node,Graph edge,vector<int>&beg)
{
    queue<int>q;
    vector<bool>check(N+1,false);
    q.push(need_node);
    check[need_node]=true;
    int cnt=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        beg[x]=++cnt;
        for(auto [node,w]:edge[x])
        {
            if(check[node])continue;
            check[node]=true;
            q.push(node);
        }
    }
}
struct node
{
    long long x;
    int bonus,index;
    node(int _x=0,int _index=0,int _bonus=0)
    {
        x=_x,index=_index,bonus=_bonus;
    }
};
bool cmp(node &a,node &b)
{
    return (a.x*(3-a.bonus)<b.x*(3-b.bonus));
}
int Onlyone(int N,long long K,Graph edge,vector<long long>distX,vector<long long>distY)
{
    int ans=0;
    vector<long long>q;
    for(int i=1; i<=N; i++)
    {
        q.push_back(distX[i]);
        q.push_back(distY[i]);
    }
    sort(q.begin(),q.end());
    for(long long value:q)
    {
        if(K>=value)
        {
            K-=value;
            ans++;
        }
    }
    return ans;
}
int Sub2(int N,int X,int Y,long long K,Graph edge,vector<int>deg,vector<long long >distX,vector<long long>distY)
{
    int need_node;
    for(int i=1; i<=N; i++)if(deg[i]==1)need_node=i;
    vector<int>beg(N+1);
    bfs(N,need_node,edge,beg);
    if(beg[X]>beg[Y])swap(X,Y);
    int pre=Onlyone(N,K,edge,distX,distY);
    vector<node>block;
    vector<int>cnt(N+1,0);
    int ans=0;
    vector<int>index(N+1);
    for(int i=1; i<=N; i++)index[beg[i]]=i;
    for(int i=1; i<=N; i++)
    {
        if((beg[i]>=beg[X]&&beg[i]<=beg[Y]))continue;
        long long value_x=min(distX[i],distY[i]);
        long long value_y=max(distX[i],distY[i]);
        if(value_y-value_x>=value_x)
        {
            block.push_back({value_x,i,1});
            block.push_back({value_y-value_x,i,1});
        }
        else block.push_back({value_y,i,2});
    }
    for(int i=beg[X]; i<=beg[Y]; i++)
    {
        int node=index[i];
        long long value_x=min(distX[node],distY[node]);
        long long value_y=max(distX[node],distY[node]);
        K-=value_x;
        ans++;
        cnt[node]=1;
        block.push_back({value_y-value_x,node,1});
    }
    sort(block.begin(),block.end(),cmp);
    if(K>=0)
    {
        for(node &need:block)
        {
            if(K>=need.x)
            {
                K-=need.x;
                cnt[need.index]+=need.bonus;
                ans+=need.bonus;
                need.bonus=0;
            }
        }
        set<pair<long long,int> >s;
        for(node need:block)if(need.bonus==2)s.insert(make_pair(min(distX[need.index],distY[need.index]),need.index));
        for(auto [value,index]:s)
        {
            if(K>=value)
            {
                K-=value;
                ans+=1;
                cnt[index]+=1;
            }
        }
        multiset<long long>pX,pY;
        for(int i=1; i<=N; i++)
        {
            if(cnt[i]==0)pY.insert(max(distX[i],distY[i]));
            if(beg[i]>=beg[X]&&beg[i]<=beg[Y])continue;
            if(cnt[i]==1)pX.insert(min(distX[i],distY[i]));
        }
        while(pX.size()>0&&pY.size()>0)
        {
            auto value_x=prev(pX.end());
            auto value_y=pY.begin();
            long long value=*value_y-*value_x;
            if(K>=value)
            {
                K-=value;
                ans++;
                pX.erase(value_x);
                pY.erase(value_y);
            }
            else break;
        }
        pre=max(ans,pre);
    }
    return pre;

}
long long dp[M][2*M+7];
int Sub3(int N,int X,int Y,long long K,Graph edge,vector<long long>distX,vector<long long>distY)
{
    int pre=Onlyone(N,K,edge,distX,distY);
    queue<int>q;
    q.push(X);
    vector<int>trace(N+1);
    vector<bool>check(N+1,false);
    vector<int>beg(N+1);
    bfs(N,X,edge,beg);
    vector<int>index(N+1);
    for(int i=1;i<=N;i++)index[beg[i]]=i;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(auto [value,node]:edge[x])
        {
            if(!check[node])
            {
                check[node]=true;
                trace[node]=x;
                q.push(node);
            }
        }
    }
    for(int i=1;i<=N;i++)check[i]=false;
    int need_node=Y;
    while(need_node!=X)
    {
        check[need_node]=true;
        need_node=trace[need_node];
    }
    check[X]=true;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=0;i<=N-1;i++)
    {
        for(int cnt=0;cnt<=2*i;cnt++)
        {
            int node=index[i+1];
            if(check[node])
            {
                dp[i+1][cnt+1]=min(dp[i][cnt+1],dp[i-1][cnt]+min(distX[node],distY[node]));
                dp[i+1][cnt+2]=min(dp[i][cnt+2],dp[i-1][cnt]+max(distX[node],distY[node]));
            }
            else
            {
                dp[i+1][cnt]=min(dp[i][cnt],dp[i-1][cnt]);
                dp[i+1][cnt+1]=min(dp[i][cnt+1],dp[i-1][cnt]+min(distX[node],distY[node]));
                dp[i+1][cnt+2]=min(dp[i][cnt+2],dp[i-1][cnt]+max(distX[node],distY[node]));
            }
        }
    }
    int ans=0;
    for(int i=0;i<=2*N;i++)if(dp[N][i]<=K)ans=i;
    ans=max(ans,pre);
    return ans;
}
int max_score(int N,int X,int Y,long long K,vector<int>U,vector<int>V,vector<int>W)
{
    X+=1;
    Y+=1;
    Graph edge(N+1);
    for(int i=1; i<=N-1; i++)
    {
        int x=U[i-1]+1;
        int y=V[i-1]+1;
        int value=W[i-1];
        edge[x].push_back({y,value});
        edge[y].push_back({x,value});
    }
    vector<long long>distX(N+1);
    vector<long long>distY(N+1);
    dfs(X,0,edge,distX);
    dfs(Y,0,edge,distY);
    if(distX[Y]>2*K)return Sub1(N,K,distX,distY);
    vector<int>deg(N+1);
    if(checkLinear(N,edge,deg))return Sub2(N,X,Y,K,edge,deg,distX,distY);
    return Sub3(N,X,Y,K,edge,distX,distY);
}
/*signed main()
{
    int n,x,y,k;
    vector<int>U;
    vector<int>V;
    vector<int>W;
    cin>>n>>x>>y>>k;
    for(int i=1; i<=n-1; i++)
    {
        int x;
        cin>>x;
        U.push_back(x);
    }
    for(int i=1; i<=n-1; i++)
    {
        int y;
        cin>>y;
        V.push_back(y);
    }
    for(int i=1; i<=n-1; i++)
    {
        int value;
        cin>>value;
        W.push_back(value);
    }
    cout<<max_score(n,x,y,k,U,V,W);
}*/

Compilation message

closing.cpp: In function 'int Sub2(int, int, int, long long int, Graph, std::vector<int>, std::vector<long long int>, std::vector<long long int>)':
closing.cpp:120:30: warning: narrowing conversion of 'value_x' from 'long long int' to 'int' [-Wnarrowing]
  120 |             block.push_back({value_x,i,1});
      |                              ^~~~~~~
closing.cpp:121:37: warning: narrowing conversion of '(value_y - value_x)' from 'long long int' to 'int' [-Wnarrowing]
  121 |             block.push_back({value_y-value_x,i,1});
      |                              ~~~~~~~^~~~~~~~
closing.cpp:123:31: warning: narrowing conversion of 'value_y' from 'long long int' to 'int' [-Wnarrowing]
  123 |         else block.push_back({value_y,i,2});
      |                               ^~~~~~~
closing.cpp:133:33: warning: narrowing conversion of '(value_y - value_x)' from 'long long int' to 'int' [-Wnarrowing]
  133 |         block.push_back({value_y-value_x,node,1});
      |                          ~~~~~~~^~~~~~~~
closing.cpp:105:8: warning: 'need_node' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |     bfs(N,need_node,edge,beg);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 39836 KB Output is correct
2 Correct 140 ms 44956 KB Output is correct
3 Correct 73 ms 5048 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2596 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2428 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2648 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 2 ms 2648 KB Output is correct
26 Correct 4 ms 3420 KB Output is correct
27 Correct 3 ms 3420 KB Output is correct
28 Correct 3 ms 3416 KB Output is correct
29 Correct 3 ms 3420 KB Output is correct
30 Correct 3 ms 3416 KB Output is correct
31 Correct 3 ms 3676 KB Output is correct
32 Correct 2 ms 3676 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2596 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Incorrect 1 ms 2396 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2596 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2428 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Incorrect 1 ms 2396 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2596 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2428 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 1 ms 2648 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 1 ms 2652 KB Output is correct
26 Correct 0 ms 2396 KB Output is correct
27 Correct 0 ms 2396 KB Output is correct
28 Incorrect 1 ms 2396 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
29 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2596 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2428 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 1 ms 2648 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 1 ms 2652 KB Output is correct
26 Correct 2 ms 2648 KB Output is correct
27 Correct 4 ms 3420 KB Output is correct
28 Correct 3 ms 3420 KB Output is correct
29 Correct 3 ms 3416 KB Output is correct
30 Correct 3 ms 3420 KB Output is correct
31 Correct 3 ms 3416 KB Output is correct
32 Correct 3 ms 3676 KB Output is correct
33 Correct 2 ms 3676 KB Output is correct
34 Correct 0 ms 2396 KB Output is correct
35 Correct 0 ms 2396 KB Output is correct
36 Incorrect 1 ms 2396 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2596 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2428 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 1 ms 2648 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 1 ms 2652 KB Output is correct
26 Correct 2 ms 2648 KB Output is correct
27 Correct 4 ms 3420 KB Output is correct
28 Correct 3 ms 3420 KB Output is correct
29 Correct 3 ms 3416 KB Output is correct
30 Correct 3 ms 3420 KB Output is correct
31 Correct 3 ms 3416 KB Output is correct
32 Correct 3 ms 3676 KB Output is correct
33 Correct 2 ms 3676 KB Output is correct
34 Correct 0 ms 2396 KB Output is correct
35 Correct 0 ms 2396 KB Output is correct
36 Incorrect 1 ms 2396 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -