oj.uz

Submission #846431

# Submission time Handle Problem Language Result Execution time Memory
846431 2023-09-07T14:39:29 Z oneloveforever Closing Time (IOI23_closing) C++17
29 / 100
 1000 ms 42856 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++)
        {
            if(j>beg[Y])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 600 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 151 ms 37288 KB Output is correct
2 Correct 194 ms 42856 KB Output is correct
3 Correct 75 ms 3016 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 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 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 1 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 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 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 35 ms 856 KB Output is correct
20 Correct 17 ms 344 KB Output is correct
21 Correct 22 ms 604 KB Output is correct
22 Correct 11 ms 604 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 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 1 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 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 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 35 ms 856 KB Output is correct
20 Correct 17 ms 344 KB Output is correct
21 Correct 22 ms 604 KB Output is correct
22 Correct 11 ms 604 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 11 ms 348 KB Output is correct
26 Execution timed out 1045 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 600 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 600 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 600 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 600 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 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -