Submission #810643

#	Time	Username	Problem	Language	Result	Execution time	Memory
810643		AndiR	Firefighting (NOI20_firefighting)	C++14	100 / 100	474 ms	112764 KiB

Firefighting

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const ll Nmax=3000000;

ll n, tot;
ll k;
struct node{
    bool cov;
    ll dist;
}v[Nmax];
ll sol[Nmax];
vector <pair<ll, ll>> 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(ll nod, ll p){
    ll qc=-1, qnc=0;
    for (ll 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)
                        qc=max(qc, k-ad[nod][i].second);
                }
                /// i se amana statia
                else qnc=max(qnc, v[ad[nod][i].first].dist+ad[nod][i].second);
            }
            ///are cover
            else{
                ///coverul cuprinde statia curenta
                if (v[ad[nod][i].first].dist>=ad[nod][i].second)
                    qc=max(qc, v[ad[nod][i].first].dist-ad[nod][i].second);
            }
        }
    }
    if (qc>=qnc){
        v[nod].cov=1;
        v[nod].dist=qc;
    }
    else{
        v[nod].cov=0;
        v[nod].dist=qnc;
    }
    //cout<<nod<<' '<<v[nod].cov<<' '<<v[nod].dist<<'\n';
    if (qc<qnc && p==-1)
        sol[tot++]=nod;
}
int main()
{
    cin>>n>>k;
    ll a, b, d;
    for (ll 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);
    if (n==1)
        cout<<"1\n1";
    else{
        cout<<tot<<'\n';
        for (ll 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(ll, ll)':
Firefighting.cpp:25:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (ll i=0; i<ad[nod].size(); i++){
      |                  ~^~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26
• Subtask 6: 38 / 38