# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
864100 | 2023-10-22T03:43:43 Z | Ice_man | Truck Driver (IOI23_deliveries) | C++17 | 0 ms | 0 KB |
#include <deliveries.h> #include <iostream> #include <vector> #define maxn 100005 #define maxq 300005 #define INF 1000000010 #define endl '\n' using namespace std; long long n; long long t[maxn]; long long c[maxn]; vector <pair <long long , long long> > v[maxn]; long long ans; long long pom; void dfs(long long node , long long parent = -1) { c[node] = t[node]; for(long long i = 0; i < (long long)v[node].size(); i++) { if(v[node][i].first == parent) continue; dfs(v[node][i].first , node); ans += v[node][i].second * min(c[v[node][i].first] , pom - c[v[node][i].first]); c[node] += c[v[node][i].first]; } } void init(long long N , vector <long long> U , vector <long long> V, vector <long long> W, vector <long long> T) { n = N; for(long long i = 0; i < (long long)U.size(); i++) v[U[i]].push_back({V[i] , W[i]}); for(long long i = 0; i < (long long)V.size(); i++) v[V[i]].push_back({U[i] , W[i]}); for(long long i = 0; i < n; i++) pom += t[i]; for(long long i = 0; i < n; i++) t[i] = T[i]; } long long max_time(long long S , long long X) { pom -= t[S]; t[S] = X; pom += t[S]; ans = 0; dfs(0); return ans; }