oj.uz

Submission #737540

# Submission time Handle Problem Language Result Execution time Memory
737540 2023-05-07T10:11:34 Z Ronin13 Firefighting (NOI20_firefighting) C++14
100 / 100
 2177 ms 272780 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 300001;
vector <vector <pll> > g(nmax);
int p[nmax][22];
ll d[nmax][22];
//ll len[nmax][22];
ll dp[nmax];
vector <vector <pll> > cent(nmax);
vector <ll> cur(nmax);

void dfs(int v, int e, ll last){
    p[v][0] = e;
    d[v][0] = last;
    for(int j = 1; j <= 20; j++){
        p[v][j] = p[p[v][j - 1]][j - 1];
        d[v][j] = d[v][j - 1] + d[p[v][j - 1]][j - 1];
    }
    for(auto x : g[v]){
        int to = x.f;
        if(to == e) continue;
        dp[to] = dp[v] + x.s;
        dfs(to, v, x.s);
    }
}

ll getlast(int v, ll k){
    for(int j = 20; j >= 0; j--){
        if(d[v][j] > k) continue;
        k -= d[v][j];
        v = p[v][j];
    }
    return v;
}

vector <int> sz(nmax);
vector <bool> marked(nmax);

void DFS(int v, int e){
    sz[v] = 1;
    for(auto ed : g[v]){
        int to = ed.f;
        if(to == e) continue;
        if(marked[to]) continue;
        DFS(to, v);
        sz[v] += sz[to];
    }
}


int find_cen(int v, int e, int n){
    for(auto ed : g[v]){
        int to = ed.f;
        if(to == e) continue;
        if(marked[to]) continue;
        if(sz[to] > n / 2){
            return find_cen(to, v, n);
        }
    }
    return v;
}


void DFS2(int v, int e, int lead, ll cur){
    cent[v].pb({lead, cur});
    for(auto x : g[v]){
        int to = x.f;
        if(to == e) continue;
        if(marked[to]) continue;
        DFS2(to, v, lead, cur + x.s);
    }
}

void upd(int v){
    for(auto to : cent[v]){
        cur[to.f] = min(cur[to.f], to.s);
    }
}

ll getans(int v){
    ll mn = 1e18;
    for(auto to : cent[v]){
        mn = min(mn, cur[to.f] + to.s);
    }
    return mn;
}

void decompose(int v){
    DFS(v, v);
    int x = find_cen(v, v, sz[v]);
    DFS2(x, x, x, 0);
    marked[x] = true;
    for(auto ed : g[x]){
        int to = ed.f;
        if(marked[to]) continue;
        decompose(to);
    }
}

int main(){
    int n; cin >> n;
    ll k; cin >> k;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        ll w; cin >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    for(int j= 0; j < 20; j++){
        d[0][j] = 1e12;
    }
    dfs(1, 1, 0);
    decompose(1);

    vector <pll> vec;
    for(int i= 1;i <= n; i++){
        vec.pb({dp[i], i});
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    int cnt = 0;
    vector <int> ans;
    for(int i = 1; i <= n; i++){
        cur[i] = 1e18;
    }
    for(auto x : vec){
        int to = x.s;
        ll o = getans(to);
        if(o <= k){
            continue;
        }
        cnt++;
        int v = getlast(to, k);
        upd(v);
        ans.pb(v);
    }
    cout << cnt << "\n";
    for(int to : ans){
        cout<< to << ' ';
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1654 ms 211916 KB Output is correct
2 Correct 1733 ms 212520 KB Output is correct
3 Correct 504 ms 89028 KB Output is correct
4 Correct 1622 ms 206760 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 10 ms 17876 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18004 KB Output is correct
2 Correct 9 ms 17980 KB Output is correct
3 Correct 9 ms 17876 KB Output is correct
4 Correct 8 ms 17876 KB Output is correct
5 Correct 8 ms 17976 KB Output is correct
6 Correct 10 ms 17972 KB Output is correct
7 Correct 9 ms 17876 KB Output is correct
8 Correct 9 ms 17976 KB Output is correct
9 Correct 9 ms 17876 KB Output is correct
10 Correct 10 ms 17976 KB Output is correct
11 Correct 10 ms 17876 KB Output is correct
12 Correct 9 ms 17876 KB Output is correct
13 Correct 9 ms 17972 KB Output is correct
14 Correct 9 ms 17876 KB Output is correct
15 Correct 10 ms 17876 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17976 KB Output is correct
2 Correct 10 ms 17876 KB Output is correct
3 Correct 10 ms 17976 KB Output is correct
4 Correct 9 ms 17976 KB Output is correct
5 Correct 12 ms 17972 KB Output is correct
6 Correct 12 ms 17876 KB Output is correct
7 Correct 11 ms 17972 KB Output is correct
8 Correct 12 ms 17908 KB Output is correct
9 Correct 9 ms 17876 KB Output is correct
10 Correct 9 ms 17976 KB Output is correct
11 Correct 9 ms 17876 KB Output is correct
12 Correct 9 ms 18004 KB Output is correct
13 Correct 9 ms 17876 KB Output is correct
14 Correct 10 ms 17980 KB Output is correct
15 Correct 9 ms 17976 KB Output is correct
16 Correct 9 ms 17876 KB Output is correct
17 Correct 9 ms 17972 KB Output is correct
18 Correct 9 ms 18004 KB Output is correct
19 Correct 11 ms 17876 KB Output is correct
20 Correct 9 ms 17876 KB Output is correct
21 Correct 10 ms 17888 KB Output is correct
22 Correct 11 ms 17980 KB Output is correct
23 Correct 9 ms 17876 KB Output is correct
24 Correct 10 ms 17876 KB Output is correct
25 Correct 9 ms 17976 KB Output is correct
26 Correct 10 ms 17976 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1766 ms 212504 KB Output is correct
2 Correct 860 ms 126876 KB Output is correct
3 Correct 914 ms 129852 KB Output is correct
4 Correct 750 ms 115068 KB Output is correct
5 Correct 9 ms 17976 KB Output is correct
6 Correct 9 ms 17880 KB Output is correct
7 Correct 817 ms 144344 KB Output is correct
8 Correct 794 ms 144208 KB Output is correct
9 Correct 782 ms 144348 KB Output is correct
10 Correct 823 ms 144508 KB Output is correct
11 Correct 1795 ms 212432 KB Output is correct
12 Correct 1016 ms 146640 KB Output is correct
13 Correct 574 ms 99132 KB Output is correct
14 Correct 979 ms 141364 KB Output is correct
15 Correct 1284 ms 168216 KB Output is correct
16 Correct 1357 ms 180128 KB Output is correct
17 Correct 1138 ms 155008 KB Output is correct
18 Correct 1059 ms 152064 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19284 KB Output is correct
2 Correct 14 ms 19448 KB Output is correct
3 Correct 11 ms 18560 KB Output is correct
4 Correct 12 ms 18940 KB Output is correct
5 Correct 16 ms 19924 KB Output is correct
6 Correct 16 ms 19924 KB Output is correct
7 Correct 15 ms 19924 KB Output is correct
8 Correct 18 ms 19868 KB Output is correct
9 Correct 15 ms 19828 KB Output is correct
10 Correct 16 ms 19908 KB Output is correct
11 Correct 16 ms 19984 KB Output is correct
12 Correct 12 ms 18772 KB Output is correct
13 Correct 16 ms 19924 KB Output is correct
14 Correct 16 ms 19924 KB Output is correct
15 Correct 17 ms 19652 KB Output is correct
16 Correct 13 ms 18900 KB Output is correct
17 Correct 11 ms 18772 KB Output is correct
18 Correct 15 ms 19668 KB Output is correct
19 Correct 14 ms 19180 KB Output is correct
20 Correct 13 ms 18820 KB Output is correct
21 Correct 16 ms 19656 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1621 ms 204320 KB Output is correct
2 Correct 1531 ms 196352 KB Output is correct
3 Correct 1810 ms 210448 KB Output is correct
4 Correct 603 ms 106952 KB Output is correct
5 Correct 2116 ms 269740 KB Output is correct
6 Correct 2082 ms 269896 KB Output is correct
7 Correct 2117 ms 271360 KB Output is correct
8 Correct 2059 ms 270776 KB Output is correct
9 Correct 2177 ms 261832 KB Output is correct
10 Correct 2095 ms 261392 KB Output is correct
11 Correct 2119 ms 272780 KB Output is correct
12 Correct 1010 ms 144980 KB Output is correct
13 Correct 2082 ms 270516 KB Output is correct
14 Correct 2146 ms 262252 KB Output is correct
15 Correct 1633 ms 210832 KB Output is correct
16 Correct 1491 ms 199284 KB Output is correct
17 Correct 1501 ms 197640 KB Output is correct
18 Correct 1628 ms 210888 KB Output is correct
19 Correct 1054 ms 150296 KB Output is correct
20 Correct 493 ms 93252 KB Output is correct
21 Correct 1570 ms 210428 KB Output is correct