Submission #1079159

#TimeUsernameProblemLanguageResultExecution timeMemory
1079159beaconmcClosing Time (IOI23_closing)C++17
0 / 100
42 ms12376 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,x,y) for(ll i=x; i<y; i++) #define FORNEG(i,x,y) for(ll i=x; i>y; i--) ll n; vector<vector<ll>> edges[3005]; ll dist1[3005]; ll dist2[3005]; ll dp[3005][6005]; vector<vector<ll>> dists; void dfs(ll a, ll p, ll d, ll type){ if (type==1) dist1[a] = d; else dist2[a] = d; for (auto&i : edges[a]){ if (i[0] != p) dfs(i[0], a, d+i[1], type); } } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N; FOR(i,0,N+1) edges[i].clear(), dist1[i] = 0, dist2[i] = 0; dists.clear(); FOR(i,0,N-1){ edges[U[i]].push_back({V[i], W[i]}); edges[V[i]].push_back({U[i], W[i]}); } dfs(X, -1, 0, 1); dfs(Y, -1, 0, 2); vector<ll> idkman; FOR(i,0,N){ idkman.push_back(dist1[i]); idkman.push_back(dist2[i]); } sort(idkman.begin(), idkman.end()); ll cur = 0; ll ans = 0; while (cur<idkman.size() && K-idkman[cur]>=0){ K-= idkman[cur]; ans++; cur++; } return ans; // FOR(i,0,N){ // vector<ll> temp = {}; // temp.push_back(min(dist1[i], dist2[i])); // temp.push_back(max(dist1[i], dist2[i])); // dists.push_back(temp); // } // FOR(i,0,N) FOR(j,0,2*N+1) dp[i][j] = 100000000000000000; // dp[0][0] = 0; // dp[0][1] = dists[0][0]; // dp[0][2] = dists[0][1]; // FOR(i,1,N){ // FOR(j,0,2*N+1){ // ll temp = 100000000000000000; // if (j>=1) temp = min(temp, dp[i-1][j-1]+dists[i][0]); // if (j>=2) temp = min(temp, dp[i-1][j-2]+dists[i][1]); // temp = min(temp, dp[i-1][j]); // dp[i][j] = temp; // } // } // ll ans = 0; // FOR(i,0,N){ // FOR(j,0,2*N+1){ // if (dp[i][j] <=K){ // cout << i << " " << j << endl; // cout << dp[i][j] << endl; // ans = max(ans, j); // } // } // } // return ans; }

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:53:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while (cur<idkman.size() && K-idkman[cur]>=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...