oj.uz

Submission #846422

# Submission time Handle Problem Language Result Execution time Memory
846422 2023-09-07T14:32:31 Z oneloveforever Closing Time (IOI23_closing) C++17
29 / 100
 1000 ms 42432 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);
        }
        for(int cnt=1;cnt<=min(i,beg[X])-1;cnt++)s.update(1,1,2*N,posX[cnt],make_pair(0,0));
    }
    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 2 ms 608 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 134 ms 37724 KB Output is correct
2 Correct 151 ms 42432 KB Output is correct
3 Correct 78 ms 2896 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 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 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 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 40 ms 604 KB Output is correct
20 Correct 14 ms 600 KB Output is correct
21 Correct 31 ms 604 KB Output is correct
22 Correct 12 ms 600 KB Output is correct
23 Correct 6 ms 600 KB Output is correct
24 Correct 8 ms 600 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 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 40 ms 604 KB Output is correct
20 Correct 14 ms 600 KB Output is correct
21 Correct 31 ms 604 KB Output is correct
22 Correct 12 ms 600 KB Output is correct
23 Correct 6 ms 600 KB Output is correct
24 Correct 8 ms 600 KB Output is correct
25 Correct 13 ms 344 KB Output is correct
26 Execution timed out 1060 ms 1368 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 2 ms 608 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 2 ms 608 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 2 ms 608 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 2 ms 608 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 2 ms 608 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -