oj.uz

Submission #1046074

# Submission time Handle Problem Language Result Execution time Memory
1046074 2024-08-06T09:43:18 Z c2zi6 Petrol stations (CEOI24_stations) C++14
0 / 100
 35 ms 14036 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<bool> VB;
typedef vector<VB> VVB;
 
int n, k;
VVPI gp;
VVL dp;
VI sbt;

void addnode(int u, int v, int w) {
    replr(j, 0, k) {
        if (j < w) dp[u][k-w] += dp[v][j];
        else dp[u][j-w] += dp[v][j];
    }
}
void remnode(int u, int v, int w) {
    replr(j, 0, k) {
        if (j < w) dp[u][k-w] -= dp[v][j];
        else dp[u][j-w] -= dp[v][j];
    }
}

VL ans;
void dfs(int u = 0, int p = -1) {
    sbt[u] = 1;
    dp[u][k]++;
    for (auto[v, w] : gp[u]) if (v != p) {
        dfs(v, u);
        addnode(u, v, w);
        sbt[u] += sbt[v];

        ll contr = 0;
        rep(j, w) contr += dp[v][j];
        ans[v] += contr * (n-sbt[v]);
        /*cout << "PROCESSING EDGE " << v << " " << u << ": " << contr << " * " << (n-sbt[v]) << endl;*/
    }
}
void reroot(int u = 0, int p = -1) {
    for (auto[v, w] : gp[u]) if (v != p) {
        remnode(u, v, w);
        addnode(v, u, w);

        ll contr = 0;
        rep(j, w) contr += dp[u][j];
        ans[u] += contr * (sbt[u]-1);
        /*cout << "PROCESSING EDGE " << u << " " << v << ": " << contr << " * " << (sbt[u]-1) << endl;*/

        reroot(v, u);
        
        remnode(v, u, w);
        addnode(u, v, w);
    }
}

void solve() {
    cin >> n >> k;
    gp = VVPI(n);
    rep(i, n-1) {
        int u, v, w;
        cin >> u >> v >> w;
        gp[u].pb({v, w});
        gp[v].pb({u, w});
    }
    dp = VVL(n, VL(k+1));
    /* dp[u][x]
     * how many roads visit city u with fuel x (form subtree of u)
     */
    ans = VL(n);
    sbt = VI(n);
    dfs();
    reroot();
    for (ll x : ans) cout << x << " "; cout << endl;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	/*freopen("mincross.in", "r", stdin); */
	/*freopen("test.out", "w", stdout); */
	int t = 1;
	/*cin >> t; */
	while (t--) solve();
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for (auto[v, w] : gp[u]) if (v != p) {
      |              ^
Main.cpp: In function 'void reroot(int, int)':
Main.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for (auto[v, w] : gp[u]) if (v != p) {
      |              ^
Main.cpp: In function 'void solve()':
Main.cpp:104:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  104 |     for (ll x : ans) cout << x << " "; cout << endl;
      |     ^~~
Main.cpp:104:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  104 |     for (ll x : ans) cout << x << " "; cout << endl;
      |                                        ^~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 18.0

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

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 35 ms 14036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 35 ms 14036 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 31 ms 10536 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 31 ms 10536 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 5 ms 5724 KB Output isn't correct
4 Halted 0 ms 0 KB -