oj.uz

Submission #524115

# Submission time Handle Problem Language Result Execution time Memory
524115 2022-02-08T16:29:23 Z qwerasdfzxcl Firefighting (NOI20_firefighting) C++14
100 / 100
 1611 ms 196860 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<pair<int, ll>> adj[300300];
pair<int, ll> sp[300300][20];
ll dep[300300];
priority_queue<pair<ll, int>> pq;

struct Cent{
    ll dist[300300][20], mn[300300];
    int cpa[300300], sz[300300], cdep[300300];
    bool visited[300300];

    int getsz(int s, int pa = -1){
        sz[s] = 1;
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) sz[s] += getsz(v, s);
        return sz[s];
    }
    int getcent(int s, int cap, int pa = -1){
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa && sz[v]*2>cap) return getcent(v, cap, s);
        return s;
    }
    void getdist(int s, int dep, int pa = 0){
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa){
            dist[v][dep] = dist[s][dep] + w;
            getdist(v, dep, s);
        }
    }

    int init(int s, int dep = 0){
        getsz(s);
        int cent = getcent(s, sz[s]);

        cdep[cent] = dep;
        getdist(cent, dep);
        visited[cent] = 1;
        mn[cent] = 1e18;

        for (auto &[v, w]:adj[cent]) if (!visited[v]){
            int nxt = init(v, dep+1);
            cpa[nxt] = cent;
        }
        return cent;
    }

    void update(int s){
        for (int cur=s;cur;cur=cpa[cur]){
            mn[cur] = min(mn[cur], dist[s][cdep[cur]]);
        }
    }

    ll query(int s){
        ll ret = 1e18;
        for (int cur=s;cur;cur=cpa[cur]){
            ret = min(ret, dist[s][cdep[cur]] + mn[cur]);
        }
        return ret;
    }
}cent;

void dfs(int s, int pa = -1){
    for (auto &v:adj[s]) if (v.first!=pa){
        sp[v.first][0] = {s, v.second};
        dep[v.first] = dep[s] + v.second;
        dfs(v.first, s);
    }
}

void sp_init(int n){
    for (int j=1;j<20;j++){
        for (int i=1;i<=n;i++){
            sp[i][j].first = sp[sp[i][j-1].first][j-1].first;
            sp[i][j].second = sp[i][j-1].second + sp[sp[i][j-1].first][j-1].second;
        }
    }
}

int main(){
    int n;
    ll D;
    scanf("%d %lld", &n, &D);
    for (int i=0;i<n-1;i++){
        int x, y;
        ll z;
        scanf("%d %d %lld", &x, &y, &z);
        adj[x].emplace_back(y, z);
        adj[y].emplace_back(x, z);
    }
    if (n==1) {printf("1\n1\n"); return 0;}

    dfs(1);
    for (int i=1;i<=n;i++) pq.emplace(dep[i], i);

    cent.init(1);
    sp_init(n);

    vector<int> ans;
    while(!pq.empty()){
        auto cur = pq.top(); pq.pop();
        if (cent.query(cur.second) <= D) continue;

        int s = cur.second;
        ll rem = D;
        for (int j=19;j>=0;j--) if (sp[s][j].first && sp[s][j].second<=rem){
            rem -= sp[s][j].second;
            s = sp[s][j].first;
        }

        ans.push_back(s);
        cent.update(s);
    }

    printf("%d\n", (int)ans.size());
    for (auto &x:ans) printf("%d ", x);
    return 0;
}

Compilation message

Firefighting.cpp: In member function 'int Cent::getsz(int, int)':
Firefighting.cpp:17:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) sz[s] += getsz(v, s);
      |                    ^
Firefighting.cpp: In member function 'int Cent::getcent(int, int, int)':
Firefighting.cpp:21:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa && sz[v]*2>cap) return getcent(v, cap, s);
      |                    ^
Firefighting.cpp: In member function 'void Cent::getdist(int, int, int)':
Firefighting.cpp:25:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa){
      |                    ^
Firefighting.cpp: In member function 'int Cent::init(int, int)':
Firefighting.cpp:40:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         for (auto &[v, w]:adj[cent]) if (!visited[v]){
      |                    ^
Firefighting.cpp: In function 'int main()':
Firefighting.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d %lld", &n, &D);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Firefighting.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d %d %lld", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1147 ms 182624 KB Output is correct
2 Correct 1204 ms 182616 KB Output is correct
3 Correct 334 ms 72080 KB Output is correct
4 Correct 1154 ms 177960 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7388 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 4 ms 7368 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 7364 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 4 ms 7364 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 5 ms 7372 KB Output is correct
14 Correct 4 ms 7372 KB Output is correct
15 Correct 4 ms 7288 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7364 KB Output is correct
4 Correct 4 ms 7364 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7352 KB Output is correct
7 Correct 4 ms 7364 KB Output is correct
8 Correct 4 ms 7244 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 7364 KB Output is correct
12 Correct 5 ms 7416 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 7372 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 7372 KB Output is correct
23 Correct 4 ms 7360 KB Output is correct
24 Correct 4 ms 7400 KB Output is correct
25 Correct 4 ms 7372 KB Output is correct
26 Correct 4 ms 7372 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1189 ms 182692 KB Output is correct
2 Correct 573 ms 106324 KB Output is correct
3 Correct 586 ms 111768 KB Output is correct
4 Correct 511 ms 97616 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 554 ms 183532 KB Output is correct
8 Correct 569 ms 183392 KB Output is correct
9 Correct 560 ms 183540 KB Output is correct
10 Correct 557 ms 183448 KB Output is correct
11 Correct 1181 ms 189420 KB Output is correct
12 Correct 698 ms 128360 KB Output is correct
13 Correct 375 ms 83472 KB Output is correct
14 Correct 668 ms 123044 KB Output is correct
15 Correct 891 ms 147928 KB Output is correct
16 Correct 953 ms 158648 KB Output is correct
17 Correct 813 ms 135360 KB Output is correct
18 Correct 722 ms 133012 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8708 KB Output is correct
2 Correct 7 ms 8904 KB Output is correct
3 Correct 6 ms 8128 KB Output is correct
4 Correct 6 ms 8524 KB Output is correct
5 Correct 10 ms 9292 KB Output is correct
6 Correct 8 ms 9292 KB Output is correct
7 Correct 9 ms 9208 KB Output is correct
8 Correct 8 ms 9292 KB Output is correct
9 Correct 11 ms 9164 KB Output is correct
10 Correct 8 ms 9164 KB Output is correct
11 Correct 8 ms 9284 KB Output is correct
12 Correct 6 ms 8188 KB Output is correct
13 Correct 8 ms 9300 KB Output is correct
14 Correct 8 ms 9168 KB Output is correct
15 Correct 8 ms 9164 KB Output is correct
16 Correct 6 ms 8396 KB Output is correct
17 Correct 5 ms 8140 KB Output is correct
18 Correct 7 ms 9292 KB Output is correct
19 Correct 7 ms 8652 KB Output is correct
20 Correct 7 ms 8268 KB Output is correct
21 Correct 9 ms 9144 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 171364 KB Output is correct
2 Correct 1165 ms 170228 KB Output is correct
3 Correct 1285 ms 183272 KB Output is correct
4 Correct 512 ms 89124 KB Output is correct
5 Correct 1604 ms 193168 KB Output is correct
6 Correct 1554 ms 192180 KB Output is correct
7 Correct 1611 ms 194480 KB Output is correct
8 Correct 1541 ms 193728 KB Output is correct
9 Correct 1548 ms 189452 KB Output is correct
10 Correct 1550 ms 188816 KB Output is correct
11 Correct 1484 ms 196860 KB Output is correct
12 Correct 746 ms 125276 KB Output is correct
13 Correct 1362 ms 191564 KB Output is correct
14 Correct 1495 ms 188572 KB Output is correct
15 Correct 1145 ms 184552 KB Output is correct
16 Correct 1043 ms 173944 KB Output is correct
17 Correct 1038 ms 171668 KB Output is correct
18 Correct 1173 ms 184356 KB Output is correct
19 Correct 704 ms 130912 KB Output is correct
20 Correct 342 ms 78080 KB Output is correct
21 Correct 1116 ms 184288 KB Output is correct