oj.uz

Submission #1060372

# Submission time Handle Problem Language Result Execution time Memory
1060372 2024-08-15T13:28:00 Z dozer Closing Time (IOI23_closing) C++17
0 / 100
 183 ms 23380 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " " 
#define endl "\n"
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W)
{
    vector<pii> adj[N + 5];
    vector<ll> dist1(N, -1), dist2(N, -1);
    vector<ll> par1(N, -1), par2(N, -1);

    for (ll i = 0; i < N - 1; i++){
        adj[U[i]].pb({V[i], W[i]});
        adj[V[i]].pb({U[i], W[i]});
    }

    priority_queue<pair<ll, ll>> q;
    q.push({0, X});

    while(!q.empty()){
        pii tmp = q.top();
        q.pop();
        ll top = tmp.nd, d = -tmp.st;
        dist1[top] = d;
        for (auto i : adj[top]){
            ll v = i.st, w = i.nd;
            if (dist1[v] != -1) continue;
            par1[v] = top;
            q.push({-(d + w), v});
        }
    }

     q.push({0, Y});

     ll ans = 0;

    while(!q.empty()){
        pii tmp = q.top();
        q.pop();
        ll top = tmp.nd, d = -tmp.st;
        dist2[top] = d;
        for (auto i : adj[top]){
            ll v = i.st, w = i.nd;
            if (dist2[v] != -1) continue;
            par2[v] = top;
            q.push({-(d + w), v});
        }
    }

    for(ll i = 0; i < (1<<N); i++){
        vector<ll> v;
        ll sum = 0, res = 0;
        for (ll j = 0; j < N; j++){
            if (i & (1<<j)){
                res++;
                if (dist1[j] > dist2[j]) swap(dist1[j], dist2[j]), swap(par1[j], par2[j]);
                if (par1[j] == -1 || (i & (1<<par1[j]))){
                    sum += dist1[j];
                    if (par2[j] == -1 || (i & (1<<par2[j]))){
                        v.pb(dist2[j] - dist1[j]);
                    }
                }
                else if (par2[j] == -1 || (i & (1<<par2[j]))){
                    sum += dist2[j];
                }
                else{
                    res--;
                }
               
            }
        }

        sort(v.begin(), v.end());
        ll it = 0;
        while(it < v.size() && sum + v[it] <= K) {
            sum += v[it], res++;
            it++;
        }
        if (sum <= K) ans = max(ans, res);
    }
    return ans;
}

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:89:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         while(it < v.size() && sum + v[it] <= K) {
      |               ~~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 23380 KB 1st lines differ - on the 1st token, expected: '451', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 177 ms 348 KB Output is correct
3 Correct 168 ms 348 KB Output is correct
4 Correct 144 ms 408 KB Output is correct
5 Correct 65 ms 348 KB Output is correct
6 Incorrect 63 ms 344 KB 1st lines differ - on the 1st token, expected: '96', found: '68'
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 177 ms 348 KB Output is correct
3 Correct 168 ms 348 KB Output is correct
4 Correct 144 ms 408 KB Output is correct
5 Correct 65 ms 348 KB Output is correct
6 Incorrect 63 ms 344 KB 1st lines differ - on the 1st token, expected: '96', found: '68'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 177 ms 348 KB Output is correct
3 Correct 168 ms 348 KB Output is correct
4 Correct 144 ms 408 KB Output is correct
5 Correct 65 ms 348 KB Output is correct
6 Incorrect 63 ms 344 KB 1st lines differ - on the 1st token, expected: '96', found: '68'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 177 ms 348 KB Output is correct
4 Correct 168 ms 348 KB Output is correct
5 Correct 144 ms 408 KB Output is correct
6 Correct 65 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 34 ms 348 KB Output is correct
11 Correct 88 ms 348 KB Output is correct
12 Correct 7 ms 348 KB Output is correct
13 Correct 183 ms 344 KB Output is correct
14 Correct 112 ms 416 KB Output is correct
15 Incorrect 47 ms 344 KB 1st lines differ - on the 1st token, expected: '11', found: '13'
16 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 177 ms 348 KB Output is correct
4 Correct 168 ms 348 KB Output is correct
5 Correct 144 ms 408 KB Output is correct
6 Correct 65 ms 348 KB Output is correct
7 Incorrect 63 ms 344 KB 1st lines differ - on the 1st token, expected: '96', found: '68'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 177 ms 348 KB Output is correct
4 Correct 168 ms 348 KB Output is correct
5 Correct 144 ms 408 KB Output is correct
6 Correct 65 ms 348 KB Output is correct
7 Incorrect 63 ms 344 KB 1st lines differ - on the 1st token, expected: '96', found: '68'
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 177 ms 348 KB Output is correct
4 Correct 168 ms 348 KB Output is correct
5 Correct 144 ms 408 KB Output is correct
6 Correct 65 ms 348 KB Output is correct
7 Incorrect 63 ms 344 KB 1st lines differ - on the 1st token, expected: '96', found: '68'
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 177 ms 348 KB Output is correct
4 Correct 168 ms 348 KB Output is correct
5 Correct 144 ms 408 KB Output is correct
6 Correct 65 ms 348 KB Output is correct
7 Incorrect 63 ms 344 KB 1st lines differ - on the 1st token, expected: '96', found: '68'
8 Halted 0 ms 0 KB -