oj.uz

Submission #1069798

# Submission time Handle Problem Language Result Execution time Memory
1069798 2024-08-22T09:00:10 Z vjudge1 Petrol stations (CEOI24_stations) C++17
36 / 100
 3500 ms 17076 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 70000;

int ans[MAX_N], clones[MAX_N], k, n, num[MAX_N];
vector<vector<pair<int,int>>>adjL(MAX_N);
vector<int>vec, vec2;
vector<bool>visited;

int dfs(int pos, int fuel) {
    visited[pos] = 1;
    int tmp = 1;
    for(pair<int,int>p: adjL[pos]) {
        if(visited[p.first]) continue;
        if(fuel < p.second) {
            int X = dfs(p.first, k - p.second);
            ans[pos] += X;
            tmp += X;
        } else tmp += dfs(p.first, fuel - p.second);
    }
    return tmp;
}

void calc(int pos, int prev) {
    for(pair<int,int>p: adjL[pos]) {
        if(p.first == prev) continue;
        vec.push_back(vec.back() + p.second);
        vec2.push_back(p.first);
        calc(p.first, pos);
        num[pos] += num[p.first];
    }
}

void calc2(int pos, int prev, int cnt) {
    int brk = upper_bound(vec.begin(), vec.end(), vec[cnt] + k) - vec.begin();
    if(brk == vec.size()) return;
    else {
        --brk;
        clones[vec2[brk]] += clones[pos];
        ans[vec2[brk]] += (num[vec2[brk]] - 1) * clones[pos];
    }
    for(pair<int,int>p: adjL[pos]) {
        if(p.first == prev) continue;
        calc2(p.first, pos, cnt + 1);
    }
}

void solve() {
    cin >> n >> k;
    for(int i=0; i<n-1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adjL[u].push_back({v, w});
        adjL[v].push_back({u, w});
    }
    if(n <= 1000) {
        for(int i=0; i<n; ++i) {
            visited.assign(n, 0);
            dfs(i, k);
        }
    } else {
        for(int i=0; i<n; ++i) {
            if(adjL[i].size() == 1) {
                for(int i=0; i<n; ++i) clones[i] = num[i] = 1;
                vec.push_back(0);
                vec2.push_back(i);
                calc(i, i);
                calc2(i, i, 0);
                vec.clear();
                vec2.clear();
            }
        }
    }
    for(int i=0; i<n; ++i) cout << ans[i] << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    while(t--) solve();
}

Compilation message

Main.cpp: In function 'void calc2(long long int, long long int, long long int)':
Main.cpp:39:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if(brk == vec.size()) return;
      |        ~~~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 6 ms 2136 KB Output is correct
4 Correct 11 ms 2140 KB Output is correct
5 Correct 11 ms 2140 KB Output is correct
6 Correct 16 ms 2268 KB Output is correct
7 Correct 13 ms 2136 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 8 ms 2140 KB Output is correct
10 Correct 9 ms 2140 KB Output is correct
11 Correct 9 ms 2144 KB Output is correct
12 Correct 9 ms 2140 KB Output is correct
13 Correct 9 ms 2140 KB Output is correct
14 Correct 6 ms 2140 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 144 ms 16808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 144 ms 16808 KB Output is correct
5 Correct 117 ms 17076 KB Output is correct
6 Correct 131 ms 16828 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Execution timed out 3567 ms 9520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Execution timed out 3567 ms 9520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 6 ms 2136 KB Output is correct
4 Correct 11 ms 2140 KB Output is correct
5 Correct 11 ms 2140 KB Output is correct
6 Correct 16 ms 2268 KB Output is correct
7 Correct 13 ms 2136 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 8 ms 2140 KB Output is correct
10 Correct 9 ms 2140 KB Output is correct
11 Correct 9 ms 2144 KB Output is correct
12 Correct 9 ms 2140 KB Output is correct
13 Correct 9 ms 2140 KB Output is correct
14 Correct 6 ms 2140 KB Output is correct
15 Correct 1 ms 1884 KB Output is correct
16 Correct 144 ms 16808 KB Output is correct
17 Correct 117 ms 17076 KB Output is correct
18 Correct 131 ms 16828 KB Output is correct
19 Execution timed out 3567 ms 9520 KB Time limit exceeded
20 Halted 0 ms 0 KB -