oj.uz

답안 #810639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810639 2023-08-06T13:09:21 Z AndiR Firefighting (NOI20_firefighting) C++14
36 / 100
 450 ms 96644 KB 
#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=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

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.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 440 ms 96180 KB Output is correct
2 Correct 407 ms 96076 KB Output is correct
3 Correct 139 ms 80392 KB Output is correct
4 Correct 430 ms 95420 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 32 ms 70736 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 70756 KB Output is correct
2 Correct 31 ms 70748 KB Output is correct
3 Correct 32 ms 70680 KB Output is correct
4 Correct 40 ms 70808 KB Output is correct
5 Correct 33 ms 70744 KB Output is correct
6 Correct 40 ms 70700 KB Output is correct
7 Correct 53 ms 70636 KB Output is correct
8 Correct 51 ms 70708 KB Output is correct
9 Correct 32 ms 70740 KB Output is correct
10 Correct 33 ms 70756 KB Output is correct
11 Correct 32 ms 70740 KB Output is correct
12 Correct 32 ms 70748 KB Output is correct
13 Correct 33 ms 70740 KB Output is correct
14 Correct 32 ms 70700 KB Output is correct
15 Correct 33 ms 70748 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 70756 KB Output is correct
2 Correct 34 ms 70668 KB Output is correct
3 Correct 41 ms 70664 KB Output is correct
4 Correct 33 ms 70664 KB Output is correct
5 Correct 36 ms 70868 KB Output is correct
6 Correct 33 ms 70652 KB Output is correct
7 Correct 35 ms 70732 KB Output is correct
8 Correct 33 ms 70768 KB Output is correct
9 Correct 37 ms 70672 KB Output is correct
10 Correct 33 ms 70676 KB Output is correct
11 Correct 33 ms 70732 KB Output is correct
12 Correct 33 ms 70760 KB Output is correct
13 Correct 34 ms 70704 KB Output is correct
14 Correct 34 ms 70712 KB Output is correct
15 Correct 34 ms 70740 KB Output is correct
16 Correct 38 ms 70724 KB Output is correct
17 Correct 37 ms 70676 KB Output is correct
18 Correct 33 ms 70740 KB Output is correct
19 Correct 34 ms 70748 KB Output is correct
20 Correct 33 ms 70728 KB Output is correct
21 Correct 32 ms 70728 KB Output is correct
22 Correct 32 ms 70748 KB Output is correct
23 Correct 32 ms 70760 KB Output is correct
24 Correct 33 ms 70736 KB Output is correct
25 Correct 32 ms 70740 KB Output is correct
26 Correct 32 ms 70752 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 418 ms 96152 KB Output is correct
2 Correct 200 ms 83952 KB Output is correct
3 Correct 185 ms 84508 KB Output is correct
4 Correct 200 ms 82584 KB Output is correct
5 Correct 31 ms 70700 KB Output is correct
6 Correct 31 ms 70660 KB Output is correct
7 Correct 312 ms 92876 KB Output is correct
8 Correct 307 ms 92848 KB Output is correct
9 Correct 319 ms 92924 KB Output is correct
10 Correct 360 ms 93000 KB Output is correct
11 Correct 450 ms 96644 KB Output is correct
12 Correct 240 ms 87392 KB Output is correct
13 Correct 141 ms 81148 KB Output is correct
14 Correct 217 ms 86324 KB Output is correct
15 Correct 285 ms 89548 KB Output is correct
16 Correct 305 ms 90792 KB Output is correct
17 Correct 296 ms 87676 KB Output is correct
18 Correct 281 ms 87196 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 70912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 374 ms 91184 KB Output isn't correct
2 Halted 0 ms 0 KB -