oj.uz

답안 #525100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525100 2022-02-10T17:12:40 Z azberjibiou Firefighting (NOI20_firefighting) C++17
100 / 100
 321 ms 53024 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<double, double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=300005;
const int mxM=1010;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1e18;
const ll P1=1000000009;
const ll P2=1000000009;
int N;
ll K;
ll station[mxN];
ll town[mxN];
bool Chk[mxN];
vector <pll> v[mxN];
int ans;
void dfs(int now, int pre, ll dis)
{
    station[now]=INF;
    town[now]=0;
    for(pll nxt : v[now])   if(nxt.fir!=pre)
    {
        dfs(nxt.fir, now, nxt.sec);
        station[now]=min(station[now], station[nxt.fir]+nxt.sec);
        town[now]=max(town[now], town[nxt.fir]+nxt.sec);
    }
    if(now==1)
    {
        if(town[now]>K-station[now])
        {
            Chk[now]=true;
            ans++;
        }
        return;
    }
    if(town[now]<=K-station[now])   town[now]=-INF;
    if(town[now]+dis>K)
    {
        Chk[now]=true;
        ans++;
        station[now]=0;
        town[now]=-INF;
    }
}
int main()
{
    gibon
    cin >> N >> K;
    for(int i=1;i<N;i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].emplace_back(b, c);
        v[b].emplace_back(a, c);
    }
    dfs(1, -1, 0);
    cout << ans << '\n';
    for(int i=1;i<=N;i++)
    {
        if(Chk[i])  cout << i << " ";
    }
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 275 ms 30368 KB Output is correct
2 Correct 286 ms 30288 KB Output is correct
3 Correct 77 ms 15780 KB Output is correct
4 Correct 291 ms 29684 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 6 ms 7288 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 3 ms 7372 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7244 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 3 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7332 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7372 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 4 ms 7368 KB Output is correct
18 Correct 4 ms 7372 KB Output is correct
19 Correct 4 ms 7372 KB Output is correct
20 Correct 4 ms 7368 KB Output is correct
21 Correct 4 ms 7372 KB Output is correct
22 Correct 4 ms 7368 KB Output is correct
23 Correct 4 ms 7360 KB Output is correct
24 Correct 4 ms 7364 KB Output is correct
25 Correct 4 ms 7372 KB Output is correct
26 Correct 4 ms 7488 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 30352 KB Output is correct
2 Correct 127 ms 19776 KB Output is correct
3 Correct 128 ms 20204 KB Output is correct
4 Correct 106 ms 18504 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 203 ms 27968 KB Output is correct
8 Correct 212 ms 27944 KB Output is correct
9 Correct 204 ms 27944 KB Output is correct
10 Correct 202 ms 27932 KB Output is correct
11 Correct 321 ms 30476 KB Output is correct
12 Correct 168 ms 22540 KB Output is correct
13 Correct 83 ms 16868 KB Output is correct
14 Correct 151 ms 21700 KB Output is correct
15 Correct 201 ms 24900 KB Output is correct
16 Correct 212 ms 26072 KB Output is correct
17 Correct 186 ms 23108 KB Output is correct
18 Correct 165 ms 22840 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 5 ms 7500 KB Output is correct
5 Correct 5 ms 7760 KB Output is correct
6 Correct 6 ms 7756 KB Output is correct
7 Correct 5 ms 7756 KB Output is correct
8 Correct 5 ms 7756 KB Output is correct
9 Correct 5 ms 7628 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct
11 Correct 6 ms 7896 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 5 ms 7756 KB Output is correct
14 Correct 5 ms 7700 KB Output is correct
15 Correct 6 ms 7636 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 4 ms 7500 KB Output is correct
18 Correct 5 ms 7628 KB Output is correct
19 Correct 5 ms 7500 KB Output is correct
20 Correct 5 ms 7504 KB Output is correct
21 Correct 6 ms 7576 KB Output is correct

Subtask #6
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 251 ms 27512 KB Output is correct
2 Correct 251 ms 32652 KB Output is correct
3 Correct 263 ms 34700 KB Output is correct
4 Correct 98 ms 19908 KB Output is correct
5 Correct 277 ms 47176 KB Output is correct
6 Correct 277 ms 45492 KB Output is correct
7 Correct 263 ms 51012 KB Output is correct
8 Correct 272 ms 49880 KB Output is correct
9 Correct 273 ms 43552 KB Output is correct
10 Correct 270 ms 42584 KB Output is correct
11 Correct 275 ms 53024 KB Output is correct
12 Correct 162 ms 25796 KB Output is correct
13 Correct 279 ms 45180 KB Output is correct
14 Correct 272 ms 41408 KB Output is correct
15 Correct 251 ms 35132 KB Output is correct
16 Correct 238 ms 33348 KB Output is correct
17 Correct 231 ms 33156 KB Output is correct
18 Correct 262 ms 35028 KB Output is correct
19 Correct 163 ms 26436 KB Output is correct
20 Correct 105 ms 18244 KB Output is correct
21 Correct 272 ms 34952 KB Output is correct