oj.uz

Submission #810637

# Submission time Handle Problem Language Result Execution time Memory
810637 2023-08-06T13:07:12 Z AndiR Firefighting (NOI20_firefighting) C++14
36 / 100
 418 ms 33004 KB 
#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){
    ll qc=-1, qnc=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)
                        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;
    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);
    if (n==1)
        cout<<"1\n1";
    else{
        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:25: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]
   25 |     for (int i=0; i<ad[nod].size(); i++){
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 32956 KB Output is correct
2 Correct 405 ms 32972 KB Output is correct
3 Correct 141 ms 16704 KB Output is correct
4 Correct 365 ms 32200 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7360 KB Output is correct
2 Correct 3 ms 7360 KB Output is correct
3 Correct 5 ms 7252 KB Output is correct
4 Correct 3 ms 7360 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 3 ms 7252 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 3 ms 7356 KB Output is correct
9 Correct 3 ms 7356 KB Output is correct
10 Correct 3 ms 7252 KB Output is correct
11 Correct 3 ms 7252 KB Output is correct
12 Correct 3 ms 7252 KB Output is correct
13 Correct 3 ms 7352 KB Output is correct
14 Correct 3 ms 7252 KB Output is correct
15 Correct 3 ms 7252 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7352 KB Output is correct
2 Correct 3 ms 7352 KB Output is correct
3 Correct 3 ms 7356 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7360 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7252 KB Output is correct
12 Correct 3 ms 7356 KB Output is correct
13 Correct 3 ms 7284 KB Output is correct
14 Correct 4 ms 7252 KB Output is correct
15 Correct 3 ms 7252 KB Output is correct
16 Correct 3 ms 7364 KB Output is correct
17 Correct 3 ms 7352 KB Output is correct
18 Correct 3 ms 7252 KB Output is correct
19 Correct 3 ms 7252 KB Output is correct
20 Correct 3 ms 7252 KB Output is correct
21 Correct 3 ms 7252 KB Output is correct
22 Correct 4 ms 7252 KB Output is correct
23 Correct 3 ms 7252 KB Output is correct
24 Correct 3 ms 7252 KB Output is correct
25 Correct 3 ms 7360 KB Output is correct
26 Correct 3 ms 7248 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 32948 KB Output is correct
2 Correct 169 ms 19700 KB Output is correct
3 Correct 155 ms 20052 KB Output is correct
4 Correct 129 ms 18272 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7360 KB Output is correct
7 Correct 291 ms 29012 KB Output is correct
8 Correct 290 ms 28848 KB Output is correct
9 Correct 301 ms 28916 KB Output is correct
10 Correct 279 ms 28904 KB Output is correct
11 Correct 418 ms 33004 KB Output is correct
12 Correct 225 ms 22628 KB Output is correct
13 Correct 111 ms 16824 KB Output is correct
14 Correct 172 ms 21788 KB Output is correct
15 Correct 238 ms 24804 KB Output is correct
16 Correct 281 ms 26008 KB Output is correct
17 Correct 207 ms 23136 KB Output is correct
18 Correct 222 ms 22724 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 28996 KB Output isn't correct
2 Halted 0 ms 0 KB -