Submission #848470

#	Time	Username	Problem	Language	Result	Execution time	Memory
848470		oneloveforever	Closing Time (IOI23_closing)	C++17	83 / 100	784 ms	2097152 KiB

closing

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
const long long  inf=1e18+7;
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;

}
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);
    vector<bool>check(N+1,false);
    for(int i=1;i<=N;i++)if(distX[i]+distY[i]==distX[Y])check[i]=true;
    vector<vector<long long> >dp(N+7,vector<long long>(2*N+7,inf));
    dp[0][0]=0;
    for(int i=0;i<=N-1;i++)
    {
        for(int cnt=0;cnt<=2*i;cnt++)
        {
            if(check[i+1])
            {
                dp[i+1][cnt+1]=min(dp[i+1][cnt+1],dp[i][cnt]+min(distX[i+1],distY[i+1]));
                dp[i+1][cnt+2]=min(dp[i+1][cnt+2],dp[i][cnt]+max(distX[i+1],distY[i+1]));
            }
            else
            {
                dp[i+1][cnt]=min(dp[i+1][cnt],dp[i][cnt]);
                dp[i+1][cnt+1]=min(dp[i+1][cnt+1],dp[i][cnt]+min(distX[i+1],distY[i+1]));
                dp[i+1][cnt+2]=min(dp[i+1][cnt+2],dp[i][cnt]+max(distX[i+1],distY[i+1]));
            }
        }
    }
    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);
    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 (stderr)

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:119:30: warning: narrowing conversion of 'value_x' from 'long long int' to 'int' [-Wnarrowing]
  119 |             block.push_back({value_x,i,1});
      |                              ^~~~~~~
closing.cpp:120:37: warning: narrowing conversion of '(value_y - value_x)' from 'long long int' to 'int' [-Wnarrowing]
  120 |             block.push_back({value_y-value_x,i,1});
      |                              ~~~~~~~^~~~~~~~
closing.cpp:122:31: warning: narrowing conversion of 'value_y' from 'long long int' to 'int' [-Wnarrowing]
  122 |         else block.push_back({value_y,i,2});
      |                               ^~~~~~~
closing.cpp:132:33: warning: narrowing conversion of '(value_y - value_x)' from 'long long int' to 'int' [-Wnarrowing]
  132 |         block.push_back({value_y-value_x,node,1});
      |                          ~~~~~~~^~~~~~~~
closing.cpp:104:8: warning: 'need_node' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |     bfs(N,need_node,edge,beg);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 17