Submission #810541

#	Time	Username	Problem	Language	Result	Execution time	Memory
810541		AndiR	Firefighting (NOI20_firefighting)	C++14	0 / 100	451 ms	33020 KiB

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 (stderr)

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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26
• Subtask 6: 0 / 38