oj.uz

Submission #1056584

# Submission time Handle Problem Language Result Execution time Memory
1056584 2024-08-13T10:10:33 Z Ignut Closing Time (IOI23_closing) C++17
9 / 100
 1000 ms 34232 KB 
/* Ignut
started: 13.08.2024
now: 13.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 2e5 + 123;

vector<pair<int, int>> tree[MAXN];

ll dx[MAXN], dy[MAXN];

void dfs(int v, int par, ll d, bool f) {
    if (f) dx[v] = d;
    else dy[v] = d;
    for (auto [to, w] : tree[v])
        if (to != par)
            dfs(to, v, d + w, f);
}

bool takeX[MAXN];
bool takeY[MAXN];

void dfsX(int v) {
    takeX[v] = true;
    for (auto [to, w] : tree[v])
        if (dx[to] < dx[v])
            dfsX(to);
}

void dfsY(int v) {
    takeY[v] = true;
    for (auto [to, w] : tree[v])
        if (dy[to] < dy[v])
            dfsY(to);
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < N; i ++)
        tree[i].clear();
    for (int i = 0; i < N - 1; i ++) {
        tree[U[i]].push_back({V[i], W[i]});
        tree[V[i]].push_back({U[i], W[i]});
    }
    dfs(X, -1, 0, true);
    dfs(Y, -1, 0, false);

    int res = 0;
    for (int mask = 0; mask < 1 << N; mask ++) {
        for (int i = 0; i < N; i ++) takeX[i] = takeY[i] = false;
        ll sum = 0;
        int ans = 0;
        for (int i = 0; i < N; i ++) {
            if (mask & (1 << i)) {
                dfsX(i);
                dfsY(i);
            }
        }
        vector<ll> ds;
        for (int i = 0; i < N; i ++) {
            ans += takeX[i] + takeY[i];
            if (takeX[i] && takeY[i]) sum += max(dx[i], dy[i]);
            else if (takeX[i] && !takeY[i]) sum += dx[i];
            else if (!takeX[i] && takeY[i]) sum += dy[i];

            if (!takeX[i]) ds.push_back(dx[i]);
            if (!takeY[i]) ds.push_back(dy[i]);
        }
        sort(ds.begin(), ds.end());
        for (int i = 0; i < ds.size(); i ++) {
            if (sum + ds[i] <= K) {
                sum += ds[i];
                ans ++;
            }
        }
        if (sum <= K) res = max(res, ans);
    }
    return res;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for (int i = 0; i < ds.size(); i ++) {
      |                         ~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 29900 KB Output is correct
2 Correct 99 ms 34232 KB Output is correct
3 Execution timed out 1099 ms 10972 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8284 KB Output is correct
2 Correct 621 ms 8460 KB Output is correct
3 Correct 798 ms 8472 KB Output is correct
4 Correct 988 ms 8464 KB Output is correct
5 Correct 420 ms 8284 KB Output is correct
6 Correct 724 ms 8284 KB Output is correct
7 Incorrect 77 ms 8468 KB 1st lines differ - on the 1st token, expected: '26', found: '21'
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8284 KB Output is correct
2 Correct 621 ms 8460 KB Output is correct
3 Correct 798 ms 8472 KB Output is correct
4 Correct 988 ms 8464 KB Output is correct
5 Correct 420 ms 8284 KB Output is correct
6 Correct 724 ms 8284 KB Output is correct
7 Incorrect 77 ms 8468 KB 1st lines differ - on the 1st token, expected: '26', found: '21'
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8284 KB Output is correct
2 Correct 621 ms 8460 KB Output is correct
3 Correct 798 ms 8472 KB Output is correct
4 Correct 988 ms 8464 KB Output is correct
5 Correct 420 ms 8284 KB Output is correct
6 Correct 724 ms 8284 KB Output is correct
7 Incorrect 77 ms 8468 KB 1st lines differ - on the 1st token, expected: '26', found: '21'
8 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 1 ms 8284 KB Output is correct
3 Correct 621 ms 8460 KB Output is correct
4 Correct 798 ms 8472 KB Output is correct
5 Correct 988 ms 8464 KB Output is correct
6 Correct 420 ms 8284 KB Output is correct
7 Correct 1 ms 8284 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 1 ms 8488 KB Output is correct
10 Correct 146 ms 8468 KB Output is correct
11 Correct 290 ms 8540 KB Output is correct
12 Correct 14 ms 8280 KB Output is correct
13 Correct 695 ms 8484 KB Output is correct
14 Correct 281 ms 8284 KB Output is correct
15 Correct 169 ms 8468 KB Output is correct
16 Correct 121 ms 8284 KB Output is correct
17 Correct 135 ms 8464 KB Output is correct
18 Correct 329 ms 8464 KB Output is correct
19 Correct 711 ms 8468 KB Output is correct
20 Correct 168 ms 8284 KB Output is correct
21 Correct 155 ms 8464 KB Output is correct
22 Correct 666 ms 8468 KB Output is correct
23 Correct 757 ms 8284 KB Output is correct
24 Correct 154 ms 8280 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 1 ms 8284 KB Output is correct
3 Correct 621 ms 8460 KB Output is correct
4 Correct 798 ms 8472 KB Output is correct
5 Correct 988 ms 8464 KB Output is correct
6 Correct 420 ms 8284 KB Output is correct
7 Correct 724 ms 8284 KB Output is correct
8 Incorrect 77 ms 8468 KB 1st lines differ - on the 1st token, expected: '26', found: '21'
9 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 1 ms 8284 KB Output is correct
3 Correct 621 ms 8460 KB Output is correct
4 Correct 798 ms 8472 KB Output is correct
5 Correct 988 ms 8464 KB Output is correct
6 Correct 420 ms 8284 KB Output is correct
7 Correct 724 ms 8284 KB Output is correct
8 Incorrect 77 ms 8468 KB 1st lines differ - on the 1st token, expected: '26', found: '21'
9 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 1 ms 8284 KB Output is correct
3 Correct 621 ms 8460 KB Output is correct
4 Correct 798 ms 8472 KB Output is correct
5 Correct 988 ms 8464 KB Output is correct
6 Correct 420 ms 8284 KB Output is correct
7 Correct 724 ms 8284 KB Output is correct
8 Incorrect 77 ms 8468 KB 1st lines differ - on the 1st token, expected: '26', found: '21'
9 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 1 ms 8284 KB Output is correct
3 Correct 621 ms 8460 KB Output is correct
4 Correct 798 ms 8472 KB Output is correct
5 Correct 988 ms 8464 KB Output is correct
6 Correct 420 ms 8284 KB Output is correct
7 Correct 724 ms 8284 KB Output is correct
8 Incorrect 77 ms 8468 KB 1st lines differ - on the 1st token, expected: '26', found: '21'
9 Halted 0 ms 0 KB -