Submission #810541

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
810541	2023-08-06T10:57:47 Z	AndiR	Firefighting (NOI20_firefighting)	C++14	0 / 100	451 ms	33020 KB

Firefighting

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const int Nmax=300000;

int n, tot;
ll k;
struct node{
    bool cov;
    ll dist;
}v[Nmax];
int sol[Nmax];
vector <pair<int, int>> ad[Nmax];

void cmp(bool& t, ll& mx, bool nt, ll nmx){
    if (t>nt || t==nt && nmx>mx){
        t=nt;
        mx=nmx;
    }
}
void dfs(int nod, int p){
    bool t=1;
    ll mx=0;
    for (int i=0; i<ad[nod].size(); i++){
        if (ad[nod][i].first!=p){
            dfs(ad[nod][i].first, nod);
            /// nu are cover
            if (v[ad[nod][i].first].cov==0){
                ///trb sa ii se puna statie
                if (v[ad[nod][i].first].dist+ad[nod][i].second>k){
                    sol[tot++]=ad[nod][i].first;
                    if (ad[nod][i].second>k)
                        cmp(t, mx, 0, 0);
                    else cmp (t, mx, 1, ad[nod][i].second);
                }
                /// i se amana statia
                else cmp(t, mx, 0, v[ad[nod][i].first].dist+ad[nod][i].second);
            }
            ///are cover
            else{
                ///coverul nu cuprinde si statia curenta
                if (v[ad[nod][i].first].dist+ad[nod][i].second>k)
                    cmp(t, mx, 0, 0);
                ///coverul cuprinde statia curenta
                else cmp(t, mx, 1, v[ad[nod][i].first].dist+ad[nod][i].second);
            }
        }
    }
    if (ad[nod].size()!=1 || p==-1){
        v[nod].dist=mx;
        v[nod].cov=t;
    }
    //cout<<nod<<' '<<v[nod].cov<<' '<<v[nod].dist<<'\n';
    if (t==0 && p==-1)
        sol[tot++]=nod;
}
int main()
{
    cin>>n>>k;
    int a, b, d;
    for (int i=1; i<n; i++){
        cin>>a>>b>>d;
        a--; b--;
        ad[a].push_back({b, d});
        ad[b].push_back({a, d});
    }
    dfs(0, -1);
    cout<<tot<<'\n';
    for (int i=0; i<tot; i++)
        cout<<sol[i]+1<<' ';
    return 0;
}

Compilation message

Firefighting.cpp: In function 'void cmp(bool&, ll&, bool, ll)':
Firefighting.cpp:18:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |     if (t>nt || t==nt && nmx>mx){
      |                 ~~~~~~^~~~~~~~~
Firefighting.cpp: In function 'void dfs(int, int)':
Firefighting.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i=0; i<ad[nod].size(); i++){
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	380 ms	33020 KB	Output is correct
2	Correct	375 ms	32932 KB	Output is correct
3	Correct	113 ms	16652 KB	Output is correct
4	Correct	451 ms	32188 KB	Output is correct
5	Correct	4 ms	7360 KB	Output is correct
6	Incorrect	5 ms	7252 KB	Integer parameter [name=F] equals to 0, violates the range [1, 1]
7	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7252 KB	Output is correct
2	Correct	4 ms	7252 KB	Output is correct
3	Incorrect	5 ms	7360 KB	Integer parameter [name=F] equals to 0, violates the range [1, 1]
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7356 KB	Output is correct
2	Correct	5 ms	7380 KB	Output is correct
3	Correct	3 ms	7252 KB	Output is correct
4	Incorrect	4 ms	7360 KB	Output isn't correct
5	Halted	0 ms	0 KB	-