Submission #1061440

#TimeUsernameProblemLanguageResultExecution timeMemory
1061440mychecksedadClosing Time (IOI23_closing)C++17
0 / 100
38 ms10056 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define ll long long #define ff first #define ss second const int N = 3005; const ll INF = 1e18; int sz[N], par[N]; vector<pair<int, ll>> g[N]; ll val1[N], val2[N], dp[N][N]; void dfs(int v, int p, vector<ll> &D){ par[v] = p; for(auto U: g[v]){ int u = U.ff; if(u != p){ D[u] = D[v] + U.ss; dfs(u, v, D); } } } vector<int> euler; bool pre(int v, int p, int t){ euler.pb(v); if(v == t){ return 1; } for(auto U: g[v]){ int u = U.ff; if(u != p){ bool ok = pre(u, v, t); if(ok) return 1; } } euler.pop_back(); return 0; } int max_score(int n, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){ for(int i = 0; i < n; ++i) g[i].clear(); euler.clear(); for(int i = 0; i < n - 1; ++i){ g[V[i]].pb({U[i], W[i]}); g[U[i]].pb({V[i], W[i]}); } if(X > Y) swap(X,Y); vector<ll> D1(n), D2(n); dfs(X, X, D1); dfs(Y, Y, D2); vector<ll> A; for(int i =0 ; i < n; ++i) A.pb(D1[i]); for(int i =0 ; i < n; ++i) A.pb(D2[i]); sort(all(A)); int anss = 0; ll tot = 0; for(int i = 0; i < A.size(); ++i){ if(tot + A[i] <= K) tot += A[i], ++anss; } pre(X, X, Y); vector<bool> s(n); for(int v: euler) s[v] = 1; for(int i = 0; i < n; ++i){ if(s[i]){ val1[i] = max(D1[i], D2[i]) - min(D1[i], D2[i]); val2[i] = -1; K -= min(D1[i], D2[i]); }else{ val1[i] = min(D1[i], D2[i]); val2[i] = max(D1[i], D2[i]) - val1[i]; } } if(K<0) return anss; // vector<ll> DP(2*n + 5, INF); // DP[0] = 0; // int S = 0; // for(int i = 0; i < n; ++i){ // S+=2; // for(int j = S; j >= 1; --j){ // DP[j] = min(DP[j], DP[j - 1] + val1[i]); // if(j > 1 && val2[i] != -1) // DP[j] = min(DP[j], DP[j - 2] + val2[i] + val1[i]); // } // } // for(int i = 2*n; i >= 0; --i){ // if(DP[i] <= K){ // return max(i + int(euler.size()), anss); // } // } set<array<ll, 3>> B; for(int i = 0; i < n; ++i){ // if(val2[i] == -1){ if(val2[i] == -1) B.insert({val1[i] * 2, i, 2}); else B.insert({val1[i] * 2, i, 1}); // } // else if(val1[i] < val2[i]){ // B.pb({val1[i] * 2, 0, 1}); // B.pb({val2[i] * 2, 0, 1}); // }else{ // B.pb({val1[i] + val2[i], val1[i], 2}); // } } // K *= 2; vector<bool> taken(n); int ans = 0; // sort(all(B)); while(B.size()){ auto it = B.begin(); auto x = *it; B.erase(it); if(taken[x[1]]) continue; if(x[2] == 1){ if(K >= x[0] / 2){ K -= x[0] / 2; ++ans; taken[x[1]] = 1; } }else if(x[2] == 2){ if(K >= x[0] / 2){ K -= x[0] / 2; ans += 1; for(auto U: g[x[1]]){ int u = U.ff; if(u != par[x[1]] && val2[u] != -1){ if(taken[u]) B.insert({2 * val2[u], u, 2}); else B.insert({val1[u] + val2[u], u, 3}); } } } }else{ if(K >= x[0]){ K -= x[0]; ans += 2; for(auto U: g[x[1]]){ int u = U.ff; if(u != par[x[1]] && val2[u] != -1){ if(taken[u]) B.insert({2 * val2[u], u, 2}); else B.insert({val1[u] + val2[u], u, 3}); } } } } } return max(ans + int(euler.size()), anss); }

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:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 0; i < A.size(); ++i){
      |                  ~~^~~~~~~~~~
#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...