Submission #1234223

#TimeUsernameProblemLanguageResultExecution timeMemory
1234223santi3223Closing Time (IOI23_closing)C++20
8 / 100
109 ms26808 KiB
#include <bits/stdc++.h> #include "closing.h" using namespace std; #define ll long long #define vb vector<bool> #define pb push_back #define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++) #define vl vector<ll> #define pll pair<ll, ll> #define fi first #define se second #define ed "\n" #define all(aaa) aaa.begin(), aaa.end() #define rall(aaa) aaa.rbegin(), aaa.rend() ll MOD = 1e9+7; priority_queue<ll, vector<ll>, greater<ll>> pq; vector<vector<pll>> conexiones; ll k; void dfs(ll cur, ll p, ll sum){ if(sum > k){ return; } pq.push(sum); for(auto &x : conexiones[cur]){ if(x.fi != p){ dfs(x.fi, cur, sum+x.se); } } } int max_score(int n, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){ conexiones = vector<vector<pll>>(n); k = K; ff(i, 0, n-1){ conexiones[U[i]].pb({V[i], W[i]}); conexiones[V[i]].pb({U[i], W[i]}); } dfs(X, -1, 0); dfs(Y, -1, 0); ll tot = 0, ktot = 0; while(ktot <= K && !pq.empty()){ ll cur = pq.top(); //cout << ktot << " " << cur << " " << K << ed; if(ktot+cur > K){ break; } else{ ktot += cur; tot++; pq.pop(); } } while(!pq.empty()){ pq.pop(); } return tot; } /* int main(){ int Q; assert(1 == scanf("%d", &Q)); std::vector<int> N(Q), X(Q), Y(Q); std::vector<long long> K(Q); std::vector<std::vector<int>> U(Q), V(Q), W(Q); for (int q = 0; q < Q; q++) { assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q])); U[q].resize(N[q] - 1); V[q].resize(N[q] - 1); W[q].resize(N[q] - 1); for (int i = 0; i < N[q] - 1; ++i) { assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i])); } } fclose(stdin); std::vector<int> result(Q); for (int q = 0; q < Q; q++) { result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]); } for (int q = 0; q < Q; q++) { printf("%d\n", result[q]); } fclose(stdout); return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...