oj.uz

Submission #894662

# Submission time Handle Problem Language Result Execution time Memory
894662 2023-12-28T15:48:14 Z JeanBombeur Closing Time (IOI23_closing) C++17
8 / 100
 133 ms 47672 KB 
#include "closing.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

//  <|°_°|>

//  M. Broccoli & JeanBombeur

const int MAX_NODES = 2e5;

struct event {
    long long cost;
    int node, id;
};

vector <pair <int, long long>> Adj[MAX_NODES];

long long Dist[2][MAX_NODES];
bool Taken[2][MAX_NODES];

vector <int> Path;

priority_queue <event> Greedy;

bool operator<(event a, event b) {
    return a.cost > b.cost;
}

bool Dfs(int id, int node, int parent = -1, int target = -1) {
    for (pair <int, long long> dest : Adj[node])
    {
        if (dest.first != parent)
        {
            Dist[id][dest.first] = Dist[id][node] + dest.second;
            if (Dfs(id, dest.first, node, target))
                target = node;
        }
    }
    if (node == target)
        Path.push_back(node);
    return node == target;
}

int RunSmart(int answer, long long maxSum) {
    long long last = 0;
    long long sum = 0;
    while (!Greedy.empty())
    {
        auto [cost, node, id] = Greedy.top();
        Greedy.pop();
        if (id == 2)
        {
            if (Taken[0][node] || Taken[1][node])
                continue;
            cost *= 2;
            if ((sum += cost) <= maxSum)
            {
                answer += 2;
                Taken[0][node] = Taken[1][node] = 1;
            }
            else if (sum - last <= maxSum)
            {
                answer ++;
                break;
            }
            else
                break;
        }
        else
        {
            if (Taken[id][node])
                continue;
            if ((sum += cost) > maxSum)
                break;
            Taken[id][node] = 1;
            answer ++;
            if (!Taken[id ^ 1][node])
                Greedy.push({Dist[id ^ 1][node] - Dist[id][node], node, id ^ 1});
        }
        last = cost;
    }
    return answer;
}

int max_score(int nbNodes, int start1, int start2, long long maxSum,
    vector <int> Left, vector <int> Right, vector <int> Weight) {
    
    maxSum <<= 1;
    
    Path.clear();
    for (int i = 0; i < nbNodes; i ++)
        Adj[i].clear();
    for (int i = 0; i < nbNodes - 1; i ++)
    {
        Adj[Left[i]].emplace_back(Right[i], Weight[i] << 1);
        Adj[Right[i]].emplace_back(Left[i], Weight[i] << 1);
    }
    for (int id = 0; id < 2; id ++)
    {
        fill_n(Dist[id], nbNodes, 0LL);
        fill_n(Taken[id], nbNodes, 0);
        if (!id)
            Dfs(id, start1);
        else
            Dfs(id, start2, -1, start1);
    }
    
    int answer = 0;
    long long sum = 0;
    int greed = 0;
    vector <long long> mini;
    for (int i = 0; i < nbNodes; i ++)
    {
        mini.push_back(Dist[0][i]);
        mini.push_back(Dist[1][i]);
    }
    sort(mini.begin(), mini.end());
    for (long long a : mini)
        if ((sum += a) <= maxSum)
            greed ++;
    
    while (!Greedy.empty())
        Greedy.pop();
    sum = 0;
    for (int a : Path)
    {
        int id = Dist[0][a] > Dist[1][a];
        sum += Dist[id][a];
        answer ++;
        Taken[id][a] = 1;
        Greedy.push({Dist[id ^ 1][a] - Dist[id][a], a, id ^ 1});
    }
    if (sum > maxSum)
        return greed;
    
    for (int i = 0; i < nbNodes; i ++)
    {
        int id = Dist[0][i] > Dist[1][i];
        Greedy.push({Dist[id][i], i, id});
        Greedy.push({Dist[id ^ 1][i] / 2, i, 2});
    }
    
    return max(greed, RunSmart(answer, maxSum - sum));
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 35852 KB Output is correct
2 Correct 133 ms 47672 KB Output is correct
3 Correct 67 ms 10252 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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