제출 #1000446

#제출 시각아이디문제언어결과실행 시간메모리
1000446thelegendary08봉쇄 시간 (IOI23_closing)C++17
8 / 100
121 ms33380 KiB
#include "closing.h" #include<bits/stdc++.h> #define f0r(i,n) for(int i = 0;i<n;i++) #define FOR(i, k, n) for(int i = k;i<n;i++) #define pb push_back #define vi vector<long long int> #define ll long long int using namespace std; int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { vector<pair<ll,ll>> adj[N]; f0r(i, N-1){ adj[U[i]].pb({V[i], W[i]}); adj[V[i]].pb({U[i], W[i]}); } vector<vector<ll>>dist(N, vector<ll>(2, 4e18)); vector<bool>vis(N, 0); queue<int>q; q.push(X); vis[X] = 1; dist[X][0] = 0; while(!q.empty()){ int c = q.front(); q.pop(); for(auto u : adj[c]){ if(vis[u.first])continue; vis[u.first] = 1; dist[u.first][0] = min(dist[u.first][0], dist[c][0] + u.second); q.push(u.first); } } f0r(i,N)vis[i] = 0; vis[Y] = 1; dist[Y][1] = 0; q.push(Y); while(!q.empty()){ int c = q.front(); q.pop(); for(auto u : adj[c]){ if(vis[u.first])continue; vis[u.first] = 1; dist[u.first][1] = min(dist[u.first][1], dist[c][1] + u.second); q.push(u.first); } } if(dist[Y][0] > 2 * K){ vector<ll> dists; f0r(i, N){ dists.pb(min(dist[i][0], dist[i][1])); } sort(dists.begin(), dists.end()); int ans = 0; ll s = 0; f0r(i, N){ if(s + dists[i] > K)break; ans++; s += dists[i]; } return ans; } else{ ll ps[N+1][3]; int ans = 0; ps[0][0] = 0; ps[0][1] = 0; ps[0][2] = 0; FOR(i, 1, N+1){ ps[i][0] = ps[i-1][0] + dist[i-1][0]; ps[i][1] = ps[i-1][1] + dist[i-1][1]; ps[i][2] = ps[i-1][2] + max(dist[i-1][0], dist[i-1][1]); } vi ps2; f0r(i, N+1){ ps2.pb(ps[i][1]); } //f0r(i, N+1)cout<<ps[i][0]<<' '; //cout<<'\n'; f0r(i, N+1){ //cout<<ps2[i]<<' '; //cout<<ps[i][1]<<' '; } //cout<<'\n'; f0r(l1, X+1){ f0r(l2, Y){ FOR(r1, X, N){ if((l2<=r1 && K < ps[l2+1][0] - ps[l1][0] + ps[r1 + 1][2] - ps[l2][2]) || (l2 > r1 && K < ps[r1 + 1][0] - ps[l1][0]))continue; if(l2 <= r1){ ll mx = K - (ps[l2+1][0] - ps[l1][0] + ps[r1 + 1][2] - ps[l2][2]) + ps[r1][1]; int r2 = upper_bound(ps2.begin(), ps2.end(), mx) - ps2.begin(); r2-=2; if(r2 < Y)continue; //if(r1 + r2 - l1 - l2 + 2 == 2)cout<<l1<<' '<<l2<<' '<<r1<<' '<<r2<<'\n'; ans = max(ans, r1 + r2 - l1 - l2 + 2); } else{ ll mx = K - (ps[r1 + 1][0] - ps[l1][0]) + ps[l2][1]; int r2 = upper_bound(ps2.begin(), ps2.end(), mx) - ps2.begin(); r2 -= 2; if(r2 < Y)continue; //if(r1 + r2 - l1 - l2 + 2 == 2)cout<<mx<<' '<<l1<<' '<<l2<<' '<<r1<<' '<<r2<<'\n'; ans = max(ans, r1 + r2 - l1 - l2 + 2); } } } } return ans; } }
#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...