# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
810643 | 2023-08-06T13:20:04 Z | AndiR | Firefighting (NOI20_firefighting) | C++14 | 474 ms | 112764 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=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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 403 ms | 95784 KB | Output is correct |
2 | Correct | 380 ms | 95756 KB | Output is correct |
3 | Correct | 144 ms | 79976 KB | Output is correct |
4 | Correct | 365 ms | 95184 KB | Output is correct |
5 | Correct | 30 ms | 70740 KB | Output is correct |
6 | Correct | 30 ms | 70708 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 70684 KB | Output is correct |
2 | Correct | 32 ms | 70660 KB | Output is correct |
3 | Correct | 31 ms | 70696 KB | Output is correct |
4 | Correct | 32 ms | 70748 KB | Output is correct |
5 | Correct | 32 ms | 70708 KB | Output is correct |
6 | Correct | 31 ms | 70732 KB | Output is correct |
7 | Correct | 30 ms | 70640 KB | Output is correct |
8 | Correct | 30 ms | 70764 KB | Output is correct |
9 | Correct | 30 ms | 70748 KB | Output is correct |
10 | Correct | 31 ms | 70768 KB | Output is correct |
11 | Correct | 31 ms | 70668 KB | Output is correct |
12 | Correct | 31 ms | 70676 KB | Output is correct |
13 | Correct | 30 ms | 70732 KB | Output is correct |
14 | Correct | 30 ms | 70664 KB | Output is correct |
15 | Correct | 30 ms | 70748 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 70780 KB | Output is correct |
2 | Correct | 29 ms | 70716 KB | Output is correct |
3 | Correct | 28 ms | 70668 KB | Output is correct |
4 | Correct | 30 ms | 70716 KB | Output is correct |
5 | Correct | 29 ms | 70724 KB | Output is correct |
6 | Correct | 31 ms | 70736 KB | Output is correct |
7 | Correct | 30 ms | 70740 KB | Output is correct |
8 | Correct | 30 ms | 70740 KB | Output is correct |
9 | Correct | 30 ms | 70644 KB | Output is correct |
10 | Correct | 31 ms | 70696 KB | Output is correct |
11 | Correct | 32 ms | 70672 KB | Output is correct |
12 | Correct | 31 ms | 70656 KB | Output is correct |
13 | Correct | 31 ms | 70648 KB | Output is correct |
14 | Correct | 30 ms | 70764 KB | Output is correct |
15 | Correct | 31 ms | 70740 KB | Output is correct |
16 | Correct | 31 ms | 70740 KB | Output is correct |
17 | Correct | 31 ms | 70652 KB | Output is correct |
18 | Correct | 31 ms | 70640 KB | Output is correct |
19 | Correct | 31 ms | 70768 KB | Output is correct |
20 | Correct | 30 ms | 70732 KB | Output is correct |
21 | Correct | 31 ms | 70728 KB | Output is correct |
22 | Correct | 35 ms | 70800 KB | Output is correct |
23 | Correct | 31 ms | 70644 KB | Output is correct |
24 | Correct | 32 ms | 70760 KB | Output is correct |
25 | Correct | 31 ms | 70700 KB | Output is correct |
26 | Correct | 32 ms | 70676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 388 ms | 95792 KB | Output is correct |
2 | Correct | 186 ms | 83564 KB | Output is correct |
3 | Correct | 173 ms | 83904 KB | Output is correct |
4 | Correct | 149 ms | 82116 KB | Output is correct |
5 | Correct | 31 ms | 70740 KB | Output is correct |
6 | Correct | 30 ms | 70740 KB | Output is correct |
7 | Correct | 297 ms | 92164 KB | Output is correct |
8 | Correct | 292 ms | 92160 KB | Output is correct |
9 | Correct | 291 ms | 92232 KB | Output is correct |
10 | Correct | 310 ms | 92180 KB | Output is correct |
11 | Correct | 387 ms | 95816 KB | Output is correct |
12 | Correct | 237 ms | 86784 KB | Output is correct |
13 | Correct | 135 ms | 80752 KB | Output is correct |
14 | Correct | 196 ms | 85756 KB | Output is correct |
15 | Correct | 256 ms | 88892 KB | Output is correct |
16 | Correct | 278 ms | 90056 KB | Output is correct |
17 | Correct | 238 ms | 86988 KB | Output is correct |
18 | Correct | 257 ms | 86572 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 70904 KB | Output is correct |
2 | Correct | 35 ms | 70868 KB | Output is correct |
3 | Correct | 31 ms | 70784 KB | Output is correct |
4 | Correct | 33 ms | 70924 KB | Output is correct |
5 | Correct | 34 ms | 71032 KB | Output is correct |
6 | Correct | 32 ms | 71096 KB | Output is correct |
7 | Correct | 38 ms | 71144 KB | Output is correct |
8 | Correct | 33 ms | 71096 KB | Output is correct |
9 | Correct | 37 ms | 70988 KB | Output is correct |
10 | Correct | 35 ms | 70988 KB | Output is correct |
11 | Correct | 33 ms | 71040 KB | Output is correct |
12 | Correct | 41 ms | 70816 KB | Output is correct |
13 | Correct | 34 ms | 71048 KB | Output is correct |
14 | Correct | 34 ms | 71000 KB | Output is correct |
15 | Correct | 33 ms | 71020 KB | Output is correct |
16 | Correct | 32 ms | 70820 KB | Output is correct |
17 | Correct | 40 ms | 70760 KB | Output is correct |
18 | Correct | 34 ms | 70996 KB | Output is correct |
19 | Correct | 32 ms | 70860 KB | Output is correct |
20 | Correct | 31 ms | 70876 KB | Output is correct |
21 | Correct | 38 ms | 70944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 395 ms | 91448 KB | Output is correct |
2 | Correct | 405 ms | 96008 KB | Output is correct |
3 | Correct | 474 ms | 98036 KB | Output is correct |
4 | Correct | 206 ms | 83348 KB | Output is correct |
5 | Correct | 394 ms | 108312 KB | Output is correct |
6 | Correct | 366 ms | 107084 KB | Output is correct |
7 | Correct | 358 ms | 110484 KB | Output is correct |
8 | Correct | 373 ms | 109676 KB | Output is correct |
9 | Correct | 367 ms | 104616 KB | Output is correct |
10 | Correct | 386 ms | 103872 KB | Output is correct |
11 | Correct | 440 ms | 112764 KB | Output is correct |
12 | Correct | 233 ms | 89024 KB | Output is correct |
13 | Correct | 407 ms | 106560 KB | Output is correct |
14 | Correct | 373 ms | 103356 KB | Output is correct |
15 | Correct | 374 ms | 98240 KB | Output is correct |
16 | Correct | 344 ms | 96484 KB | Output is correct |
17 | Correct | 359 ms | 96424 KB | Output is correct |
18 | Correct | 376 ms | 98188 KB | Output is correct |
19 | Correct | 253 ms | 89908 KB | Output is correct |
20 | Correct | 158 ms | 81608 KB | Output is correct |
21 | Correct | 372 ms | 98156 KB | Output is correct |