oj.uz

Submission #987037

# Submission time Handle Problem Language Result Execution time Memory
987037 2024-05-21T18:01:57 Z activedeltorre Closing Time (IOI23_closing) C++17
8 / 100
 173 ms 42180 KB 
#include "closing.h"
#include <queue>
using namespace std;
#include <vector>
#include <iostream>
long long dist[200005][4];
vector<pair<long long,long long> >adj[200005];
void dfs(long long curr,long long par,long long tip)
{
    for(auto k:adj[curr])
    {
        if(k.first!=par)
        {
            dist[k.first][tip]=dist[curr][tip]+k.second;
            dfs(k.first,curr,tip);
        }
    }
}
priority_queue<long long>pq;
int max_score(int N, int X, int Y, long long K,std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    long long n=N,x,y,i,w;
    for(i=0; i<=n; i++)
    {
        adj[i].clear();
    }
    for(i=0; i<n-1; i++)
    {
        x=U[i];
        y=V[i];
        w=W[i];
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    if(X>Y)
    {
        swap(X,Y);
    }
    x=X;
    y=Y;
    dist[x][0]=0;
    dist[y][1]=0;
    dfs(x,-1,0);
    dfs(y,-1,1);
    if(dist[y][0]>2*K)
    {
        for(i=0; i<n; i++)
        {
            pq.push(-dist[i][0]);
            pq.push(-dist[i][1]);
        }
        long long cnt=0;
        while(pq.size())
        {
            if(K>-pq.top())
            {
                cnt++;
                K+=pq.top();
            }
            pq.pop();
        }
        return cnt;
    }
    else
    {
        long long st,dr;
        int sol=0;
        for(st=0; st<=y; st++)
        {
            for(dr=x; dr<n; dr++)
            {
                long long sum=0;
                int cnt=0;
                for(i=st; i<=dr; i++)
                {
                    sum-=min(dist[i][0],dist[i][1]);
                }
                for(i=x;i<=dr;i++)
                {
                    sum+=dist[i][0];
                    cnt++;
                }
                for(i=y;i>=st;i--)
                {
                    sum+=dist[i][1];
                    cnt++;
                }
                if(sum<=K)
                {
                    for(i=min(x-1,st-1); i>=0; i--)
                    {
                        pq.push(-dist[i][0]);
                    }
                    for(i=max(y+1,dr+1); i<n; i++)
                    {
                        pq.push(-dist[i][1]);
                    }
                    while(pq.size())
                    {
                        if(sum-pq.top()<=K)
                        {
                            sum-=pq.top();
                            cnt++;
                        }
                        pq.pop();
                    }
                    sol=max(sol,cnt);
                }
            }
        }
        return sol;
    }
    return 0;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 37300 KB Output is correct
2 Correct 168 ms 42180 KB Output is correct
3 Correct 79 ms 9296 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Incorrect 3 ms 6748 KB 1st lines differ - on the 1st token, expected: '30', found: '22'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Incorrect 3 ms 6748 KB 1st lines differ - on the 1st token, expected: '30', found: '22'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Incorrect 3 ms 6748 KB 1st lines differ - on the 1st token, expected: '30', found: '22'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Incorrect 3 ms 6748 KB 1st lines differ - on the 1st token, expected: '30', found: '22'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Incorrect 3 ms 6748 KB 1st lines differ - on the 1st token, expected: '30', found: '22'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Incorrect 3 ms 6748 KB 1st lines differ - on the 1st token, expected: '30', found: '22'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Incorrect 3 ms 6748 KB 1st lines differ - on the 1st token, expected: '30', found: '22'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Incorrect 3 ms 6748 KB 1st lines differ - on the 1st token, expected: '30', found: '22'
4 Halted 0 ms 0 KB -