Submission #952345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952345	2024-03-23T15:15:43 Z	vjudge306	Firefighting (NOI20_firefighting)	C++17	14 / 100	647 ms	1048576 KB

Firefighting

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define intt int _; cin >> _; while (_--)
#define emp push_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define ld long double
#define A first
#define B second
//#define int long long
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));

int main() {

    x_x
    int n,K; cin>>n>>K; ll dis[n+2][n+2];
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) dis[i][j]=1e15;
    }
    for (int i=1,a,b,c; i<n; i++) cin>>a>>b>>c, dis[a][b]=c, dis[b][a]=c;
    int nm=(1<<n); int f[n+2]={}; ll d[n+2][n+2];
    vector<int>ans;
    for (int i=1; i<=n; i++) ans.emp(i);

    for (int z=1; z<nm; z++) {

        for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
           d[i][j]=dis[i][j];
        }
    }
    int in=0;
        for (int i=0; i<n; i++) {
            if (z&(1<<i)) f[i+1]=1, d[i+1][i+1]=0, in++; else f[i+1]=0;
        }
        for (int k=1; k<=n; k++) {
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) d[i][j]=min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    bool ok=1;
    for (int i=1; i<=n; i++) {
        ll mn=LLONG_MAX;
        for (int j=1; j<=n; j++) {
            if (f[j])mn=min(mn, d[i][j]);
        }
        if(mn>K) {ok=0; break;}
    }
    if(ok&&in<ans.size()) {
        ans.clear(); for(int i=1; i<=n; i++) if (f[i]) ans.emp(i);
    }
    }
    cout<<ans.size()<<nn;
    for(auto i:ans)cout<<i<<' ';
  return 0;
}

Compilation message

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     if(ok&&in<ans.size()) {
      |            ~~^~~~~~~~~~~

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	506 ms	1048576 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	636 ms	436 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	266 ms	436 KB	Output is correct
6	Correct	254 ms	436 KB	Output is correct
7	Correct	600 ms	432 KB	Output is correct
8	Correct	647 ms	432 KB	Output is correct
9	Correct	619 ms	436 KB	Output is correct
10	Correct	644 ms	348 KB	Output is correct
11	Correct	630 ms	348 KB	Output is correct
12	Correct	613 ms	432 KB	Output is correct
13	Correct	592 ms	428 KB	Output is correct
14	Correct	20 ms	344 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	588 ms	432 KB	Output is correct
2	Correct	577 ms	344 KB	Output is correct
3	Correct	595 ms	436 KB	Output is correct
4	Correct	251 ms	432 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	600 KB	Output is correct
9	Correct	630 ms	436 KB	Output is correct
10	Correct	618 ms	436 KB	Output is correct
11	Correct	0 ms	544 KB	Output is correct
12	Correct	596 ms	428 KB	Output is correct
13	Correct	260 ms	432 KB	Output is correct
14	Correct	261 ms	436 KB	Output is correct
15	Correct	608 ms	596 KB	Output is correct
16	Correct	256 ms	432 KB	Output is correct
17	Correct	611 ms	432 KB	Output is correct
18	Correct	278 ms	592 KB	Output is correct
19	Correct	625 ms	436 KB	Output is correct
20	Correct	622 ms	432 KB	Output is correct
21	Correct	623 ms	596 KB	Output is correct
22	Correct	626 ms	344 KB	Output is correct
23	Correct	636 ms	432 KB	Output is correct
24	Correct	601 ms	436 KB	Output is correct
25	Correct	575 ms	432 KB	Output is correct
26	Correct	617 ms	436 KB	Output is correct