oj.uz

답안 #847697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
847697 2023-09-10T07:54:09 Z TheMiraiTraveller0711 봉쇄 시간 (IOI23_closing) C++17
37 / 100
 1000 ms 251216 KB 
#include "closing.h"
#include <bits/stdc++.h>
// #include <vector>
using namespace std;
using ll = long long;

bool isSub1;

// Subtask Checker
class CheckSub1
{
private:
    vector<vector<pair<int, ll>>> adj;
    vector<bool> vis;
    vector<ll> dist;

    void DFS(int u, ll dd)
    {
        vis[u] = 1;
        dist[u] = dd;
        for (auto [v, w] : adj[u])
        {
            if (vis[v])
                continue;
            DFS(v, dd + w);
        }
    }

public:
    bool isSub1(int N, int X, int Y, long long K,
                vector<int> U, vector<int> V, vector<int> W)
    {
        adj.resize(N + 3);
        dist.resize(N + 3);
        vis.assign(N + 3, 0);
        for (int i = 0; i < N - 1; i++)
        {
            adj[U[i]].push_back({V[i], W[i]});
            adj[V[i]].push_back({U[i], W[i]});
        }
        DFS(X, 0);
        return (dist[Y] > 2 * K);
    }
};

/*
Subtask 1 :
*/
class Subtask1
{
private:
    vector<vector<pair<int, ll>>> adj;
    vector<bool> vis;
    void DFS(int u, ll dd, vector<ll> &dist)
    {
        vis[u] = 1;
        dist[u] = dd;
        for (auto [v, w] : adj[u])
        {
            if (vis[v])
                continue;
            DFS(v, dd + w, dist);
        }
    }

public:
    int getsol(int N, int X, int Y, long long K,
               vector<int> U, vector<int> V, vector<int> W)
    {
        adj.resize(N + 3);
        for (int i = 0; i < N - 1; i++)
        {
            adj[U[i]].push_back({V[i], W[i]});
            adj[V[i]].push_back({U[i], W[i]});
        }
        vector<ll> dist1(N + 3);
        vis.assign(N + 3, 0);
        DFS(X, 0, dist1);
        vector<ll> dist2(N + 3);
        vis.assign(N + 3, 0);
        DFS(Y, 0, dist2);

        vector<ll> adist;
        for (int i = 0; i < N; i++)
        {
            adist.push_back(dist1[i]);
            adist.push_back(dist2[i]);
        }
        sort(adist.begin(), adist.end());

        int pt = 0, ans = 0;
        ll cost = 0;
        while (pt < adist.size() && cost + adist[pt] <= K)
        {
            cost += adist[pt];
            pt++, ans++;
        }
        return ans;
    }
};

// Subtask2-8
class Subtask2
{
private:
    vector<vector<pair<int, ll>>> adj;
    vector<bool> vis;
    void DFS(int u, ll dd, vector<ll> &dist, vector<int> &trace)
    {
        vis[u] = 1;
        dist[u] = dd;
        for (auto [v, w] : adj[u])
        {
            if (vis[v])
                continue;
            trace[v] = u;
            DFS(v, dd + w, dist, trace);
        }
    }

public:
    int getsol(int N, int X, int Y, long long K,
               vector<int> U, vector<int> V, vector<int> W)
    {
        adj.resize(N + 3);
        for (int i = 0; i < N - 1; i++)
        {
            adj[U[i]].push_back({V[i], W[i]});
            adj[V[i]].push_back({U[i], W[i]});
        }

        if (X > Y)
            swap(X, Y);
        vector<ll> dist1(N + 3);
        vector<int> trace1(N + 3);
        vis.assign(N + 3, 0);
        DFS(X, 0, dist1, trace1);
        vector<ll> dist2(N + 3);
        vector<int> trace2(N + 3);
        vis.assign(N + 3, 0);
        DFS(Y, 0, dist2, trace2);

        Subtask1 solver;
        ll ans = solver.getsol(N, X, Y, K, U, V, W);

        if (isSub1)
            return ans;

        vector<bool> pth(N + 3, 0);
        int gg = Y;
        while (gg != X)
        {
            pth[gg] = 1;
            gg = trace1[gg];
        }

        vector<vector<ll>> dp(4000, vector<ll>(8000, 1e18));
        dp[0][0] = 0;
        for (int i = 0; i < N; i++)
            if (pth[i])
                for (int j = 0; j <= i * 2; j++)
                {
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + min(dist1[i], dist2[i]));
                    dp[i + 1][j + 2] = min(dp[i + 1][j + 2], dp[i][j] + max(dist1[i], dist2[i]));
                }
            else
                for (int j = 0; j <= i * 2; j++)
                {
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + min(dist1[i], dist2[i]));
                    dp[i + 1][j + 2] = min(dp[i + 1][j + 2], dp[i][j] + max(dist1[i], dist2[i]));
                }

        for (int i = 0; i <= 2 * N; i++)
        {
            if (dp[N][i] <= K)
                ans = max(ans, (ll)(i));
        }

        return ans;
    }
};

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    CheckSub1 check;
    isSub1 = check.isSub1(N, X, Y, K, U, V, W);
    // if (isSub1)
    // {
    //     Subtask1 sub1;
    //     return sub1.getsol(N, X, Y, K, U, V, W);
    // }
    // else if (N <= 3000 && !isSub1)
    // {
    Subtask2 sub2;
    return sub2.getsol(N, X, Y, K, U, V, W);
    // }
}

Compilation message

closing.cpp: In member function 'int Subtask1::getsol(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         while (pt < adist.size() && cost + adist[pt] <= K)
      |                ~~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 250972 KB Output is correct

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 222 ms 73684 KB Output is correct
2 Correct 219 ms 76060 KB Output is correct
3 Correct 115 ms 3156 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 251048 KB Output is correct
2 Correct 85 ms 251024 KB Output is correct
3 Correct 82 ms 250960 KB Output is correct
4 Correct 83 ms 250968 KB Output is correct
5 Correct 84 ms 250880 KB Output is correct
6 Correct 85 ms 250920 KB Output is correct
7 Correct 84 ms 250888 KB Output is correct
8 Correct 83 ms 251080 KB Output is correct
9 Correct 83 ms 251056 KB Output is correct
10 Correct 83 ms 250992 KB Output is correct
11 Correct 95 ms 251112 KB Output is correct

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 251048 KB Output is correct
2 Correct 85 ms 251024 KB Output is correct
3 Correct 82 ms 250960 KB Output is correct
4 Correct 83 ms 250968 KB Output is correct
5 Correct 84 ms 250880 KB Output is correct
6 Correct 85 ms 250920 KB Output is correct
7 Correct 84 ms 250888 KB Output is correct
8 Correct 83 ms 251080 KB Output is correct
9 Correct 83 ms 251056 KB Output is correct
10 Correct 83 ms 250992 KB Output is correct
11 Correct 95 ms 251112 KB Output is correct
12 Correct 90 ms 250904 KB Output is correct
13 Correct 85 ms 250940 KB Output is correct
14 Correct 83 ms 251060 KB Output is correct
15 Correct 84 ms 250896 KB Output is correct
16 Correct 84 ms 250960 KB Output is correct
17 Correct 89 ms 251216 KB Output is correct
18 Execution timed out 1070 ms 251212 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 251048 KB Output is correct
2 Correct 85 ms 251024 KB Output is correct
3 Correct 82 ms 250960 KB Output is correct
4 Correct 83 ms 250968 KB Output is correct
5 Correct 84 ms 250880 KB Output is correct
6 Correct 85 ms 250920 KB Output is correct
7 Correct 84 ms 250888 KB Output is correct
8 Correct 83 ms 251080 KB Output is correct
9 Correct 83 ms 251056 KB Output is correct
10 Correct 83 ms 250992 KB Output is correct
11 Correct 95 ms 251112 KB Output is correct
12 Correct 90 ms 250904 KB Output is correct
13 Correct 85 ms 250940 KB Output is correct
14 Correct 83 ms 251060 KB Output is correct
15 Correct 84 ms 250896 KB Output is correct
16 Correct 84 ms 250960 KB Output is correct
17 Correct 89 ms 251216 KB Output is correct
18 Execution timed out 1070 ms 251212 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 250972 KB Output is correct
2 Correct 83 ms 251048 KB Output is correct
3 Correct 85 ms 251024 KB Output is correct
4 Correct 82 ms 250960 KB Output is correct
5 Correct 83 ms 250968 KB Output is correct
6 Correct 84 ms 250880 KB Output is correct
7 Correct 82 ms 250960 KB Output is correct
8 Correct 82 ms 250884 KB Output is correct
9 Correct 86 ms 250896 KB Output is correct
10 Correct 93 ms 251104 KB Output is correct
11 Correct 87 ms 250960 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 82 ms 250972 KB Output is correct
14 Correct 84 ms 250984 KB Output is correct
15 Correct 83 ms 250960 KB Output is correct
16 Correct 85 ms 250952 KB Output is correct
17 Correct 83 ms 250964 KB Output is correct
18 Correct 87 ms 251080 KB Output is correct
19 Correct 84 ms 250992 KB Output is correct
20 Correct 82 ms 251068 KB Output is correct
21 Correct 85 ms 250932 KB Output is correct
22 Correct 85 ms 250940 KB Output is correct
23 Correct 89 ms 251156 KB Output is correct
24 Correct 83 ms 250956 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 250972 KB Output is correct
2 Correct 83 ms 251048 KB Output is correct
3 Correct 85 ms 251024 KB Output is correct
4 Correct 82 ms 250960 KB Output is correct
5 Correct 83 ms 250968 KB Output is correct
6 Correct 84 ms 250880 KB Output is correct
7 Correct 85 ms 250920 KB Output is correct
8 Correct 84 ms 250888 KB Output is correct
9 Correct 83 ms 251080 KB Output is correct
10 Correct 83 ms 251056 KB Output is correct
11 Correct 83 ms 250992 KB Output is correct
12 Correct 95 ms 251112 KB Output is correct
13 Correct 90 ms 250904 KB Output is correct
14 Correct 85 ms 250940 KB Output is correct
15 Correct 83 ms 251060 KB Output is correct
16 Correct 84 ms 250896 KB Output is correct
17 Correct 84 ms 250960 KB Output is correct
18 Correct 89 ms 251216 KB Output is correct
19 Correct 82 ms 250960 KB Output is correct
20 Correct 82 ms 250884 KB Output is correct
21 Correct 86 ms 250896 KB Output is correct
22 Correct 93 ms 251104 KB Output is correct
23 Correct 87 ms 250960 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 82 ms 250972 KB Output is correct
26 Correct 84 ms 250984 KB Output is correct
27 Correct 83 ms 250960 KB Output is correct
28 Correct 85 ms 250952 KB Output is correct
29 Correct 83 ms 250964 KB Output is correct
30 Correct 87 ms 251080 KB Output is correct
31 Correct 84 ms 250992 KB Output is correct
32 Correct 82 ms 251068 KB Output is correct
33 Correct 85 ms 250932 KB Output is correct
34 Correct 85 ms 250940 KB Output is correct
35 Correct 89 ms 251156 KB Output is correct
36 Correct 83 ms 250956 KB Output is correct
37 Correct 422 ms 251108 KB Output is correct
38 Correct 167 ms 250968 KB Output is correct
39 Correct 83 ms 250960 KB Output is correct
40 Correct 88 ms 250964 KB Output is correct
41 Correct 84 ms 250972 KB Output is correct
42 Correct 83 ms 250964 KB Output is correct
43 Correct 82 ms 250964 KB Output is correct
44 Correct 85 ms 250892 KB Output is correct
45 Correct 83 ms 251080 KB Output is correct
46 Correct 86 ms 251140 KB Output is correct
47 Correct 87 ms 250964 KB Output is correct
48 Correct 84 ms 250964 KB Output is correct
49 Correct 166 ms 251072 KB Output is correct
50 Correct 419 ms 251096 KB Output is correct

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 250972 KB Output is correct
2 Correct 83 ms 251048 KB Output is correct
3 Correct 85 ms 251024 KB Output is correct
4 Correct 82 ms 250960 KB Output is correct
5 Correct 83 ms 250968 KB Output is correct
6 Correct 84 ms 250880 KB Output is correct
7 Correct 85 ms 250920 KB Output is correct
8 Correct 84 ms 250888 KB Output is correct
9 Correct 83 ms 251080 KB Output is correct
10 Correct 83 ms 251056 KB Output is correct
11 Correct 83 ms 250992 KB Output is correct
12 Correct 95 ms 251112 KB Output is correct
13 Correct 90 ms 250904 KB Output is correct
14 Correct 85 ms 250940 KB Output is correct
15 Correct 83 ms 251060 KB Output is correct
16 Correct 84 ms 250896 KB Output is correct
17 Correct 84 ms 250960 KB Output is correct
18 Correct 89 ms 251216 KB Output is correct
19 Execution timed out 1070 ms 251212 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 250972 KB Output is correct
2 Correct 83 ms 251048 KB Output is correct
3 Correct 85 ms 251024 KB Output is correct
4 Correct 82 ms 250960 KB Output is correct
5 Correct 83 ms 250968 KB Output is correct
6 Correct 84 ms 250880 KB Output is correct
7 Correct 85 ms 250920 KB Output is correct
8 Correct 84 ms 250888 KB Output is correct
9 Correct 83 ms 251080 KB Output is correct
10 Correct 83 ms 251056 KB Output is correct
11 Correct 83 ms 250992 KB Output is correct
12 Correct 95 ms 251112 KB Output is correct
13 Correct 90 ms 250904 KB Output is correct
14 Correct 85 ms 250940 KB Output is correct
15 Correct 83 ms 251060 KB Output is correct
16 Correct 84 ms 250896 KB Output is correct
17 Correct 84 ms 250960 KB Output is correct
18 Correct 89 ms 251216 KB Output is correct
19 Execution timed out 1070 ms 251212 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 250972 KB Output is correct
2 Correct 83 ms 251048 KB Output is correct
3 Correct 85 ms 251024 KB Output is correct
4 Correct 82 ms 250960 KB Output is correct
5 Correct 83 ms 250968 KB Output is correct
6 Correct 84 ms 250880 KB Output is correct
7 Correct 85 ms 250920 KB Output is correct
8 Correct 84 ms 250888 KB Output is correct
9 Correct 83 ms 251080 KB Output is correct
10 Correct 83 ms 251056 KB Output is correct
11 Correct 83 ms 250992 KB Output is correct
12 Correct 95 ms 251112 KB Output is correct
13 Correct 90 ms 250904 KB Output is correct
14 Correct 85 ms 250940 KB Output is correct
15 Correct 83 ms 251060 KB Output is correct
16 Correct 84 ms 250896 KB Output is correct
17 Correct 84 ms 250960 KB Output is correct
18 Correct 89 ms 251216 KB Output is correct
19 Execution timed out 1070 ms 251212 KB Time limit exceeded
20 Halted 0 ms 0 KB -