oj.uz

Submission #737601

# Submission time Handle Problem Language Result Execution time Memory
737601 2023-05-07T12:22:30 Z Ronin13 Firefighting (NOI20_firefighting) C++17
100 / 100
 2151 ms 270252 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(){
  ios_base::sync_with_stdio(false);cin.tie(0);
    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 1590 ms 206480 KB Output is correct
2 Correct 1797 ms 207284 KB Output is correct
3 Correct 517 ms 87980 KB Output is correct
4 Correct 1591 ms 201744 KB Output is correct
5 Correct 10 ms 17992 KB Output is correct
6 Correct 9 ms 17940 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 17916 KB Output is correct
3 Correct 11 ms 17992 KB Output is correct
4 Correct 10 ms 17876 KB Output is correct
5 Correct 10 ms 17992 KB Output is correct
6 Correct 10 ms 18004 KB Output is correct
7 Correct 10 ms 17988 KB Output is correct
8 Correct 10 ms 17984 KB Output is correct
9 Correct 10 ms 17988 KB Output is correct
10 Correct 10 ms 18004 KB Output is correct
11 Correct 10 ms 17996 KB Output is correct
12 Correct 10 ms 17984 KB Output is correct
13 Correct 10 ms 17988 KB Output is correct
14 Correct 10 ms 17988 KB Output is correct
15 Correct 11 ms 17996 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18004 KB Output is correct
2 Correct 9 ms 18004 KB Output is correct
3 Correct 10 ms 18004 KB Output is correct
4 Correct 9 ms 17992 KB Output is correct
5 Correct 10 ms 17984 KB Output is correct
6 Correct 10 ms 17988 KB Output is correct
7 Correct 9 ms 17944 KB Output is correct
8 Correct 9 ms 17988 KB Output is correct
9 Correct 10 ms 17908 KB Output is correct
10 Correct 9 ms 17992 KB Output is correct
11 Correct 10 ms 17996 KB Output is correct
12 Correct 10 ms 18004 KB Output is correct
13 Correct 10 ms 17984 KB Output is correct
14 Correct 10 ms 18000 KB Output is correct
15 Correct 9 ms 17896 KB Output is correct
16 Correct 9 ms 18004 KB Output is correct
17 Correct 9 ms 18004 KB Output is correct
18 Correct 11 ms 18004 KB Output is correct
19 Correct 11 ms 18004 KB Output is correct
20 Correct 10 ms 18004 KB Output is correct
21 Correct 10 ms 18004 KB Output is correct
22 Correct 10 ms 17992 KB Output is correct
23 Correct 10 ms 18004 KB Output is correct
24 Correct 12 ms 17992 KB Output is correct
25 Correct 9 ms 17988 KB Output is correct
26 Correct 9 ms 17988 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 207564 KB Output is correct
2 Correct 818 ms 125620 KB Output is correct
3 Correct 878 ms 128512 KB Output is correct
4 Correct 847 ms 114196 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 10 ms 17988 KB Output is correct
7 Correct 736 ms 141112 KB Output is correct
8 Correct 690 ms 141200 KB Output is correct
9 Correct 769 ms 141196 KB Output is correct
10 Correct 704 ms 141180 KB Output is correct
11 Correct 1832 ms 207308 KB Output is correct
12 Correct 1075 ms 144856 KB Output is correct
13 Correct 669 ms 98508 KB Output is correct
14 Correct 986 ms 139636 KB Output is correct
15 Correct 1220 ms 166108 KB Output is correct
16 Correct 1439 ms 177540 KB Output is correct
17 Correct 1169 ms 152892 KB Output is correct
18 Correct 1038 ms 150128 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 19516 KB Output is correct
3 Correct 16 ms 18644 KB Output is correct
4 Correct 13 ms 19004 KB Output is correct
5 Correct 15 ms 19924 KB Output is correct
6 Correct 16 ms 19924 KB Output is correct
7 Correct 14 ms 19924 KB Output is correct
8 Correct 15 ms 19960 KB Output is correct
9 Correct 15 ms 19924 KB Output is correct
10 Correct 17 ms 19884 KB Output is correct
11 Correct 17 ms 19972 KB Output is correct
12 Correct 13 ms 18772 KB Output is correct
13 Correct 15 ms 20012 KB Output is correct
14 Correct 17 ms 19916 KB Output is correct
15 Correct 15 ms 19744 KB Output is correct
16 Correct 13 ms 18900 KB Output is correct
17 Correct 13 ms 18764 KB Output is correct
18 Correct 15 ms 19664 KB Output is correct
19 Correct 15 ms 19188 KB Output is correct
20 Correct 15 ms 18900 KB Output is correct
21 Correct 14 ms 19788 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1630 ms 200668 KB Output is correct
2 Correct 1515 ms 192760 KB Output is correct
3 Correct 1653 ms 206852 KB Output is correct
4 Correct 575 ms 106876 KB Output is correct
5 Correct 2098 ms 267872 KB Output is correct
6 Correct 2106 ms 267860 KB Output is correct
7 Correct 2076 ms 269508 KB Output is correct
8 Correct 2128 ms 269072 KB Output is correct
9 Correct 2120 ms 259760 KB Output is correct
10 Correct 2074 ms 259404 KB Output is correct
11 Correct 2151 ms 270252 KB Output is correct
12 Correct 966 ms 143636 KB Output is correct
13 Correct 2104 ms 267940 KB Output is correct
14 Correct 2080 ms 259420 KB Output is correct
15 Correct 1554 ms 207348 KB Output is correct
16 Correct 1418 ms 195996 KB Output is correct
17 Correct 1473 ms 194620 KB Output is correct
18 Correct 1591 ms 207548 KB Output is correct
19 Correct 943 ms 148664 KB Output is correct
20 Correct 502 ms 93288 KB Output is correct
21 Correct 1586 ms 206816 KB Output is correct