oj.uz

답안 #1076253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1076253 2024-08-26T12:18:17 Z GrindMachine Petrol stations (CEOI24_stations) C++17
37 / 100
 93 ms 40020 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define conts continue
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) (int)a.size()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i) 
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
    x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
    x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
    return "'"+s+"'";
}

string to_string(const char *s){
    return to_string((string)s);
}

string to_string(bool b){
    return b?"true":"false";
}

template<typename A>
string to_string(A v){
    string res = "{";
    trav(x,v){
        res += to_string(x)+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
    return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << #x << " = "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;
const int K = 15;

vector<pll> adj[N];
ll dp1[N][K], dp2[N][K];

void solve(int test_case){
    ll n,k; cin >> n >> k;
    rep(i,n-1){
        ll u,v,w; cin >> u >> v >> w;
        adj[u].pb({v,w}), adj[v].pb({u,w});
    }

    vector<ll> ans(n);
    vector<ll> subsiz(n);

    auto dfs1 = [&](ll u, ll p, auto &&dfs1) -> void{
        subsiz[u] = 1;
        rep(j,k+1) dp1[u][j] = 0;
        dp1[u][k] = 1;
        for(auto [v,w] : adj[u]){
            if(v == p) conts;
            dfs1(v,u,dfs1);
            subsiz[u] += subsiz[v];
            rep(j,k+1){
                if(j >= w){
                    dp1[u][j-w] += dp1[v][j];
                }
                else{
                    dp1[u][k-w] += dp1[v][j];
                }
            }
        }

        rep(j,k+1) dp2[u][j] = dp1[u][j];
    };

    auto dfs2 = [&](ll u, ll p, auto &&dfs2) -> void{
        for(auto [v,w] : adj[u]){
            if(v == p) conts;

            rep(j,k+1){
                if(j >= w){
                    dp2[u][j-w] -= dp1[v][j];
                }
                else{
                    dp2[u][k-w] -= dp1[v][j];
                }
            }

            rep(j,k+1){
                if(j >= w){
                    dp2[v][j-w] += dp2[u][j];
                }
                else{
                    dp2[v][k-w] += dp2[u][j];
                }
            }

            rep(j,k+1){
                if(j >= w){
                    dp2[u][j-w] += dp1[v][j];
                }
                else{
                    dp2[u][k-w] += dp1[v][j];
                }
            }

            dfs2(v,u,dfs2);
        }
    };

    dfs1(0,-1,dfs1);
    dfs2(0,-1,dfs2);

    rep(u,n){
        for(auto [v,w] : adj[u]){
            ll curr[k+5];
            ll s = subsiz[v];

            if(subsiz[v] > subsiz[u]){
                s = n-subsiz[u];
                rep(j,k+1) curr[j] = dp2[v][j];
                rep(j,k+1){
                    if(j >= w){
                        curr[j-w] -= dp1[u][j];
                    }
                    else{
                        curr[k-w] -= dp1[u][j];
                    }
                }
            }
            else{
                rep(j,k+1) curr[j] = dp1[v][j];
            }

            rep(j,k+1){
                if(j >= w){
                    dp2[u][j-w] -= curr[j];
                }
                else{
                    dp2[u][k-w] -= curr[j];
                }
            }
 
            ll sum = 0;
            rep(j,w){
                sum += dp2[u][j];
            }
 
            ans[u] += sum*s;
    
            rep(j,k+1){
                if(j >= w){
                    dp2[u][j-w] += curr[j];
                }
                else{
                    dp2[u][k-w] += curr[j];
                }
            }
        }
    }

    rep(i,n) cout << ans[i] << endl;
}

int main(){
    int t = 1;
    // cin >> t;

    rep1(i,t){
        solve(i);
    }

    return 0;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #1
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Incorrect 7 ms 2904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 80 ms 30800 KB Output is correct

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 80 ms 30800 KB Output is correct
5 Runtime error 74 ms 40020 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 74 ms 25168 KB Output is correct
4 Correct 90 ms 30684 KB Output is correct
5 Correct 85 ms 31572 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 93 ms 25316 KB Output is correct
8 Correct 91 ms 25428 KB Output is correct
9 Correct 87 ms 25404 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 74 ms 25168 KB Output is correct
4 Correct 90 ms 30684 KB Output is correct
5 Correct 85 ms 31572 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 93 ms 25316 KB Output is correct
8 Correct 91 ms 25428 KB Output is correct
9 Correct 87 ms 25404 KB Output is correct
10 Correct 75 ms 25160 KB Output is correct
11 Correct 79 ms 24988 KB Output is correct
12 Correct 69 ms 25088 KB Output is correct
13 Correct 72 ms 25140 KB Output is correct
14 Correct 81 ms 24912 KB Output is correct
15 Correct 87 ms 25172 KB Output is correct
16 Correct 73 ms 24496 KB Output is correct

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Incorrect 7 ms 2904 KB Output isn't correct
4 Halted 0 ms 0 KB -