oj.uz

Submission #1039690

# Submission time Handle Problem Language Result Execution time Memory
1039690 2024-07-31T07:40:43 Z 김은성(#10990) Petrol stations (CEOI24_stations) C++17
18 / 100
 40 ms 14036 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, ll> > graph[70009];
vector<int> route;
bool ch[70009];
ll dp[70009], ans[70009], psum[70009];
void dfs(int v){
    ch[v] = 1;
    route.push_back(v);
    for(int i=0; i<graph[v].size(); i++){
        int u = graph[v][i].first;
        if(ch[u])
            continue;
        psum[route.size()] = psum[(int)route.size() - 1] + graph[v][i].second;
        dfs(u);
    }
}
int main(){
    int n, i, a, b, c, cap;
    scanf("%d %d", &n, &cap);
    for(i=1; i<n; i++){
        scanf("%d %d %d",&a, &b, &c);
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    for(i=0; i<n; i++){
        if(graph[i].size() == 1)
            break;
    }
    psum[0] = 0;
    int root = i;
    dfs(root);
    int j = 0;
    memset(dp, 0, sizeof(dp));
    for(i=0; i<n-1; i++){
        dp[i]++;
        while(j<n-2 && psum[j+1] - psum[i] <= cap)
            j++;
        if(psum[j+1] - psum[i] > cap)
        dp[j] += dp[i];
       //printf("i=%d j=%d dp[i]=%d\n", i, j, dp[i]);
    }
    for(i=0; i<n; i++){
        ans[route[i]] += (n-1-i) * (ll)(dp[i]-1);
    }
    memset(ch, 0, sizeof(ch));
    psum[0] = 0;
    root = route.back();
    route.clear();
    dfs(root);
    dp[0] = 1;
    j = 0;
    memset(dp, 0, sizeof(dp));
    for(i=0; i<n-1; i++){
        dp[i]++;
        while(j<n-2 && psum[j+1] - psum[i] <= cap)
            j++;
        if(psum[j+1] - psum[i] > cap)
        dp[j] += dp[i];
       // printf("i=%d j=%d dp[i]=%d\n", i, j, dp[i]);
    }
    for(i=0; i<n; i++){
        ans[route[i]] += (n-1-i) * (ll)(dp[i]-1);
    }
    for(i=0; i<n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(int)':
Main.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0; i<graph[v].size(); i++){
      |                  ~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d %d", &n, &cap);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d %d %d",&a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 2576 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 36 ms 13672 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 2576 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 36 ms 13672 KB Output is correct
5 Correct 40 ms 14036 KB Output is correct
6 Correct 39 ms 13524 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 2576 KB Output is correct
3 Incorrect 34 ms 9152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 2576 KB Output is correct
3 Incorrect 34 ms 9152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 2576 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -