oj.uz

Submission #1060375

# Submission time Handle Problem Language Result Execution time Memory
1060375 2024-08-15T13:29:45 Z dozer Closing Time (IOI23_closing) C++17
0 / 100
 203 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{
                    sum = K + 1;
                }
               
            }
        }

        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;
}

/*
int main()
{
    fileio();
    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);

    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));

        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);

    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }

    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);

    return 0;
}
*/

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 1 ms 348 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 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 203 ms 404 KB Output is correct
3 Correct 142 ms 344 KB Output is correct
4 Correct 150 ms 348 KB Output is correct
5 Correct 66 ms 344 KB Output is correct
6 Incorrect 66 ms 408 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
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 203 ms 404 KB Output is correct
3 Correct 142 ms 344 KB Output is correct
4 Correct 150 ms 348 KB Output is correct
5 Correct 66 ms 344 KB Output is correct
6 Incorrect 66 ms 408 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
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 203 ms 404 KB Output is correct
3 Correct 142 ms 344 KB Output is correct
4 Correct 150 ms 348 KB Output is correct
5 Correct 66 ms 344 KB Output is correct
6 Incorrect 66 ms 408 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 203 ms 404 KB Output is correct
4 Correct 142 ms 344 KB Output is correct
5 Correct 150 ms 348 KB Output is correct
6 Correct 66 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 36 ms 348 KB Output is correct
11 Correct 79 ms 344 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 165 ms 348 KB Output is correct
14 Correct 84 ms 348 KB Output is correct
15 Incorrect 35 ms 348 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 203 ms 404 KB Output is correct
4 Correct 142 ms 344 KB Output is correct
5 Correct 150 ms 348 KB Output is correct
6 Correct 66 ms 344 KB Output is correct
7 Incorrect 66 ms 408 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 203 ms 404 KB Output is correct
4 Correct 142 ms 344 KB Output is correct
5 Correct 150 ms 348 KB Output is correct
6 Correct 66 ms 344 KB Output is correct
7 Incorrect 66 ms 408 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 203 ms 404 KB Output is correct
4 Correct 142 ms 344 KB Output is correct
5 Correct 150 ms 348 KB Output is correct
6 Correct 66 ms 344 KB Output is correct
7 Incorrect 66 ms 408 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 203 ms 404 KB Output is correct
4 Correct 142 ms 344 KB Output is correct
5 Correct 150 ms 348 KB Output is correct
6 Correct 66 ms 344 KB Output is correct
7 Incorrect 66 ms 408 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
8 Halted 0 ms 0 KB -