Submission #952346

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952346	2024-03-23T15:18:18 Z	vjudge306	Firefighting (NOI20_firefighting)	C++17	17 / 100	676 ms	2396 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;
    if(n<=17) {
      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<<' ';
    }
    else {
        cout<<n<<nn; for(int i=1; i<=n; i++)cout<<i<<' ';
    }
  return 0;
}

Compilation message

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

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2396 KB	Output is correct
2	Correct	16 ms	2392 KB	Output is correct
3	Correct	7 ms	1116 KB	Output is correct
4	Correct	16 ms	2328 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	660 ms	436 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	270 ms	432 KB	Output is correct
6	Correct	267 ms	348 KB	Output is correct
7	Correct	624 ms	344 KB	Output is correct
8	Correct	648 ms	428 KB	Output is correct
9	Correct	651 ms	444 KB	Output is correct
10	Correct	676 ms	348 KB	Output is correct
11	Correct	643 ms	596 KB	Output is correct
12	Correct	627 ms	348 KB	Output is correct
13	Correct	615 ms	596 KB	Output is correct
14	Correct	21 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	618 ms	428 KB	Output is correct
2	Correct	625 ms	344 KB	Output is correct
3	Correct	620 ms	432 KB	Output is correct
4	Correct	254 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	640 ms	428 KB	Output is correct
10	Correct	649 ms	596 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	608 ms	596 KB	Output is correct
13	Correct	271 ms	348 KB	Output is correct
14	Correct	286 ms	344 KB	Output is correct
15	Correct	618 ms	432 KB	Output is correct
16	Correct	271 ms	444 KB	Output is correct
17	Correct	635 ms	348 KB	Output is correct
18	Correct	283 ms	428 KB	Output is correct
19	Correct	641 ms	596 KB	Output is correct
20	Correct	642 ms	424 KB	Output is correct
21	Correct	662 ms	428 KB	Output is correct
22	Correct	658 ms	432 KB	Output is correct
23	Correct	647 ms	428 KB	Output is correct
24	Correct	593 ms	428 KB	Output is correct
25	Correct	595 ms	432 KB	Output is correct
26	Correct	656 ms	596 KB	Output is correct