Submission #500696

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
500696	2021-12-31T19:29:57 Z	blue	Firefighting (NOI20_firefighting)	C++17	14 / 100	218 ms	286800 KB

Firefighting

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;

const ll INF = 1'000'000'000'000'000'000LL;


    vvll dist(1+3000, vll(1+3000, INF));

        vvll has_edge(1+3000, vll(1+3000, 0));


            vector< pair<int, ll> > edge[1+3000];

int main()
{
    int N, K;
    cin >> N >> K;

    // for(int i = 1; i <= N; i++) dist[i][i] = 0;


    // vvll edge(1+N, vll(1+N, 0));


    for(int e = 1; e <= N-1; e++)
    {
        int a, b, d;
        cin >> a >> b >> d;
        has_edge[a][b] = has_edge[b][a] = 1;
        // dist[a][b] = dist[b][a] = d;
        // edge[a][b] = edge[b][a] = 1;

        edge[a].push_back({b, d});
        edge[b].push_back({a, d});
    }

    for(int i = 1; i <= N; i++)
    {
        queue<int> tbv;
        tbv.push(i);
        dist[i][i] = 0;
        while(!tbv.empty())
        {
            int u = tbv.front();
            tbv.pop();

            for(auto q: edge[u])
            {
                int v = q.first;
                ll w = q.second;

                if(dist[i][v] < INF) continue;

                dist[i][v] = dist[i][u] + w;
                tbv.push(v);
            }
        }
    }

    // for(int k = 1; k <= N; k++)
    //     for(int i = 1; i <= N; i++)
    //         for(int j = 1; j <= N; j++)
    //             dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    vi par(1+N, -1);
    for(int i = 2; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(j == i) continue;
            if(dist[1][i] == dist[1][j] + dist[j][i] && has_edge[i][j] == 1)
            {
                par[i] = j;
                break;
            }
        }
    }


    vector<pair<ll, int> > V;
    for(int i = 1; i <= N; i++) V.push_back({dist[1][i], i});

    sort(V.begin(), V.end());

    vi res;

    reverse(V.begin(), V.end());

    vi covered(1+N, 0);

        // if(N >= 100) while(1);

    for(auto q: V)
    {
        int u = q.second;

        if(covered[u]) continue;

        int v = u;
        while(v != 1 && dist[par[v]][u] <= K) v = par[v];

        res.push_back(v);

        for(int i = 1; i <= N; i++)
            if(dist[i][v] <= K)
                covered[i] = 1;
    }

    cout << int(res.size()) << '\n';
    for(int r: res) cout << r << ' ';
    cout << '\n';
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	181 ms	286788 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	141520 KB	Output is correct
2	Correct	55 ms	141508 KB	Output is correct
3	Correct	57 ms	141564 KB	Output is correct
4	Correct	61 ms	141496 KB	Output is correct
5	Correct	58 ms	141512 KB	Output is correct
6	Correct	55 ms	141528 KB	Output is correct
7	Correct	56 ms	141548 KB	Output is correct
8	Correct	70 ms	141512 KB	Output is correct
9	Correct	65 ms	141580 KB	Output is correct
10	Correct	57 ms	141512 KB	Output is correct
11	Correct	56 ms	141460 KB	Output is correct
12	Correct	63 ms	141472 KB	Output is correct
13	Correct	58 ms	141556 KB	Output is correct
14	Correct	56 ms	141420 KB	Output is correct
15	Correct	61 ms	141548 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	141448 KB	Output is correct
2	Correct	59 ms	141468 KB	Output is correct
3	Correct	59 ms	141420 KB	Output is correct
4	Correct	55 ms	141544 KB	Output is correct
5	Correct	57 ms	141476 KB	Output is correct
6	Correct	64 ms	141460 KB	Output is correct
7	Correct	60 ms	141516 KB	Output is correct
8	Correct	63 ms	141660 KB	Output is correct
9	Correct	58 ms	141508 KB	Output is correct
10	Correct	56 ms	141508 KB	Output is correct
11	Correct	56 ms	141456 KB	Output is correct
12	Correct	55 ms	141500 KB	Output is correct
13	Correct	56 ms	141460 KB	Output is correct
14	Correct	58 ms	141428 KB	Output is correct
15	Correct	85 ms	141504 KB	Output is correct
16	Correct	67 ms	141512 KB	Output is correct
17	Correct	56 ms	141524 KB	Output is correct
18	Correct	55 ms	141424 KB	Output is correct
19	Correct	59 ms	141424 KB	Output is correct
20	Correct	72 ms	141468 KB	Output is correct
21	Correct	70 ms	141508 KB	Output is correct
22	Correct	64 ms	141588 KB	Output is correct
23	Correct	56 ms	141640 KB	Output is correct
24	Correct	56 ms	141480 KB	Output is correct
25	Correct	57 ms	141476 KB	Output is correct
26	Correct	57 ms	141508 KB	Output is correct