oj.uz

Submission #846414

# Submission time Handle Problem Language Result Execution time Memory
846414 2023-09-07T14:29:50 Z oneloveforever Closing Time (IOI23_closing) C++17
29 / 100
 1000 ms 43712 KB 
//#include "closing.h"
#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>>> ;
template<typename T>
bool maximize(T &a,T b)
{
    if(a<b)
    {
        a=b;
        return true;
    }
    return false;
}
void dfs(int x,int par,Graph &edge,vector<ll>&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 [node,value]:edge[i])
        {
            deg[node]++;
            maxv=max(maxv,deg[node]);
        }
    }
    return maxv<=2;

}
struct IT
{
    int n;
    vector<pair<long long,int> >st;
    IT(int _n=0)
    {
        n=_n;
        st.resize(4*n+7);
    }
    void build(int id,int x,int y)
    {
        if(x>y)return;
        if(x==y)
        {
            st[id]=make_pair(0,0);
            return ;
        }
        st[id]=make_pair(0,0);
        int mid=(x+y)/2;
        build(2*id,x,mid);
        build(2*id+1,mid+1,y);

    }
    pair<long long,int> combine(pair<long long,int> a,pair<long long,int> b)
    {
        pair<long long,int> ans;
        ans.x=a.x+b.x;
        ans.y=a.y+b.y;
        return ans;
    }
    void update(int id,int x,int y,int index,pair<long long,int> value)
    {
        if(x>index||y<index)return ;
        if(x==y)
        {
            st[id]=value;
            return ;
        }
        int mid=(x+y)/2;
        update(2*id,x,mid,index,value);
        update(2*id+1,mid+1,y,index,value);
        st[id]=combine(st[2*id],st[2*id+1]);
    }
    pair<long long,int> get(int id,int x,int y,int l,int r)
    {
        if(x>r||y<l)return make_pair(0,0);
        if(x>=l&&y<=r)return st[id];
        int mid=(x+y)/2;
        pair<long long,int> value_x=get(2*id,x,mid,l,r);
        pair<long long,int> value_y=get(2*id+1,mid+1,y,l,r);
        return combine(value_x,value_y);

    }
};
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;
    if(deg[X]>deg[Y])swap(X,Y);
    for(int i=1;i<=N;i++)if(deg[i]==1)
    {
        need_node=i;
        break;
    }
    vector<int>beg(N+1,0);
    vector<int>pos(N+1);
    beg[need_node]=1;
    queue<int>q;
    q.push(need_node);
    while(!q.empty())
    {
        int x=q.front();
        pos[beg[x]]=x;
        q.pop();
        for(auto [node,value]:edge[x])
        {
            if(!beg[node])
            {
                beg[node]=beg[x]+1;
                q.push(node);
            }
        }
    }
    vector<long long>sumX(N+1);
    vector<long long>sumY(N+1);
    for(int i=1;i<=N;i++)
    {
        sumX[i]=sumX[i-1]+min(distX[i],distY[i]);
        sumY[i]=sumY[i-1]+max(distX[i],distY[i]);
    }
    vector<int>que;
    for(int i=1;i<=N;i++)
    {
        que.push_back(distX[i]);
        que.push_back(distY[i]);
    }
    sort(que.begin(),que.end());
    vector<int>num(2*N+1,0);
    vector<int>posX(N+1),posY(N+1);
    for(int i=1;i<=N;i++)
    {
        int index_x=lower_bound(que.begin(),que.end(),distX[pos[i]])-que.begin()+1;
        int index_y=lower_bound(que.begin(),que.end(),distY[pos[i]])-que.begin()+1;
        if(!num[index_x])num[index_x]=index_x;
        else num[index_x]++;
        if(!num[index_y])num[index_y]=index_y;
        else num[index_y]++;
        posX[i]=num[index_x];
        posY[i]=num[index_y];
    }
    int ans=0;
    long long res=K;
    for(long long value:que)
    {
        if(value>res)break;
        ans++;
        res-=value;
    }
    IT s(2*N);
    for(int i=1;i<=N;i++)
    {
        for(int cnt=1;cnt<=min(i,beg[X])-1;cnt++)s.update(1,1,2*N,posX[cnt],make_pair(distX[cnt],1));
        for(int cnt=beg[Y]+1;cnt<=N;cnt++)s.update(1,1,2*N,posY[cnt],make_pair(distY[cnt],1));
        for(int j=i;j<=N;j++)
        {
            s.update(1,1,2*N,posY[j],make_pair(0,0));
            long long value=sumY[j]-sumY[i-1];
            int total=(j-i+1)*2;
            if(i-1>=beg[X])
            {
                total+=(i-beg[X]);
                value+=sumX[i-1]-sumX[beg[X]-1];
            }
            if(j<=beg[Y])
            {
                total+=(beg[Y]-j);
                value+=sumX[beg[Y]]-sumX[j];
            }
            if(value>K)continue;
            long long used=K-value;
            int x=1;
            int y=2*N;
            int res=0;
            while(x<=y)
            {
                int mid=(x+y)/2;
                pair<long long,int> value=s.get(1,1,2*N,1,mid);
                if(value.x<=used)
                {
                    res=value.y;
                    x=mid+1;
                }
                else y=mid-1;
            }
            ans=max(ans,total+res);
        }
        s.build(1,1,2*N);
    }
    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<ll>distX(N+1);
    vector<ll>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);


}

/*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 max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:225:19: warning: control reaches end of non-void function [-Wreturn-type]
  225 |     Graph edge(N+1);
      |                   ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 36316 KB Output is correct
2 Correct 150 ms 43712 KB Output is correct
3 Correct 81 ms 2788 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 35 ms 612 KB Output is correct
20 Correct 15 ms 344 KB Output is correct
21 Correct 33 ms 604 KB Output is correct
22 Correct 15 ms 604 KB Output is correct
23 Correct 7 ms 600 KB Output is correct
24 Correct 7 ms 604 KB Output is correct
25 Correct 13 ms 344 KB Output is correct
26 Execution timed out 1041 ms 1516 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -