Submission #1060075

#TimeUsernameProblemLanguageResultExecution timeMemory
1060075dozerClosing Time (IOI23_closing)C++17
0 / 100
211 ms23440 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define sp " " #define endl "\n" #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define pb push_back #define pii pair<int, int> #define st first #define nd second #define LL node * 2 #define RR node * 2 + 1 #define ll long long const int modulo = 1e9 + 7; const ll INF = 2e18 + 7; int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { vector<pii> adj[N + 5]; vector<ll> dist1(N, -1), dist2(N, -1); for (ll i = 0; i < N - 1; i++){ adj[U[i]].pb({V[i], W[i]}); adj[V[i]].pb({U[i], W[i]}); } priority_queue<pair<ll, ll>> q; q.push({0, X}); while(!q.empty()){ pii tmp = q.top(); q.pop(); ll top = tmp.nd, d = -tmp.st; dist1[top] = d; for (auto i : adj[top]){ ll v = i.st, w = i.nd; if (dist1[v] != -1) continue; q.push({-(d + w), v}); } } q.push({0, Y}); ll ans = 0; while(!q.empty()){ pii tmp = q.top(); q.pop(); ll top = tmp.nd, d = -tmp.st; dist2[top] = d; for (auto i : adj[top]){ ll v = i.st, w = i.nd; if (dist2[v] != -1) continue; q.push({-(d + w), v}); } } for(ll i = 0; i < (1<<N); i++){ vector<ll> v; ll sum = 0, res = 0; for (ll j = 0; j < N; j++){ if (i & (1<<j)){ res++; sum += min(dist1[j], dist2[j]); v.pb(max(dist1[j], dist2[j]) - min(dist1[j], dist2[j])); } } sort(v.begin(), v.end()); ll it = 0; while(it < v.size() && sum + v[it] <= K) sum += v[it], res++, it++; if (sum <= K) ans = max(ans, res); } return ans; } /* int main() { fileio(); 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; } */

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:73:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while(it < v.size() && sum + v[it] <= K) sum += v[it], res++, it++;
      |               ~~~^~~~~~~~~~
#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...