제출 #1079199

#제출 시각아이디문제언어결과실행 시간메모리
1079199beaconmc봉쇄 시간 (IOI23_closing)C++17
35 / 100
253 ms142504 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; const ll maxn = 3005; vector<vector<ll>> edges[maxn]; ll dist1[maxn]; ll dist2[maxn]; ll dp[maxn][maxn*2]; 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); } } vector<ll> stacks; set<ll> marked; bool flag = false; void dfs2(ll a, ll p, ll target){ if (flag) return; stacks.push_back(a); if (a==target) flag = true; if (flag) return; for (auto&i : edges[a]){ if (flag) return; if (i[0]==p) continue; dfs2(i[0], a, target); if (flag) return; } if (flag) return; stacks.pop_back(); } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { stacks.clear(); marked.clear(); flag = false; 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); dfs2(X,-1,Y); for (auto&i : stacks) marked.insert(i); bool flag2 = false; ll shit = 0; for (auto&i : stacks) shit += min(dist1[i], dist2[i]); if (shit > K) flag2 = true; 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; ll k = K; while (cur<idkman.size() && k-idkman[cur]>=0){ k-= idkman[cur]; ans++; cur++; } if (flag2) 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; if (!marked.count(0)) 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]); if (!marked.count(i)) temp = min(temp, dp[i-1][j]); dp[i][j] = temp; } } FOR(i,0,N){ FOR(j,0,2*N+1){ if (dp[i][j] <=K){ ans = max(ans, j); } } } return ans; }

컴파일 시 표준 에러 (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:85: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]
   85 |     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...