oj.uz

Submission #525087

# Submission time Handle Problem Language Result Execution time Memory
525087 2022-02-10T16:42:31 Z azberjibiou Firefighting (NOI20_firefighting) C++17
22 / 100
 287 ms 37060 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=1000000000000000001;
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);
        if(Chk[nxt.fir])
        {
            station[now]=min(station[now], nxt.sec);
        }
        else
        {
            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]+dis>K)
    {
        Chk[now]=true;
        town[now]=-INF;
        station[now]=0;
        ans++;
    }
    else
    {
        Chk[now]=false;
        if(town[now]<=K-station[now])   town[now]=-INF;
    }
}
int main()
{
    gibon
    cin >> N >> K;
    for(int i=1;i<N;i++)
    {
        int 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

# Verdict Execution time Memory Grader output
1 Correct 275 ms 30352 KB Output is correct
2 Correct 275 ms 30284 KB Output is correct
3 Correct 80 ms 15844 KB Output is correct
4 Correct 280 ms 29752 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7368 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Incorrect 6 ms 7372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7364 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 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 7368 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 Incorrect 5 ms 7376 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 30464 KB Output is correct
2 Correct 124 ms 19892 KB Output is correct
3 Correct 145 ms 22972 KB Output is correct
4 Correct 109 ms 20744 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7360 KB Output is correct
7 Correct 201 ms 32692 KB Output is correct
8 Correct 217 ms 32560 KB Output is correct
9 Correct 208 ms 32716 KB Output is correct
10 Correct 210 ms 32684 KB Output is correct
11 Correct 287 ms 37060 KB Output is correct
12 Correct 166 ms 25688 KB Output is correct
13 Correct 92 ms 18724 KB Output is correct
14 Correct 160 ms 24784 KB Output is correct
15 Correct 188 ms 28460 KB Output is correct
16 Correct 210 ms 30028 KB Output is correct
17 Correct 186 ms 26632 KB Output is correct
18 Correct 162 ms 26116 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 238 ms 27568 KB Output isn't correct
2 Halted 0 ms 0 KB -