Submission #1242018

#TimeUsernameProblemLanguageResultExecution timeMemory
1242018AlperenT_Closing Time (IOI23_closing)C++20
0 / 100
1098 ms35516 KiB
#include "closing.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define pb push_back #define F first #define pii pair<int,int> #define all(a) a.begin(),a.end() #define S second #define sz(a) (int)a.size() #define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++) #define per(i , a , b) for(int i = (a) ; i >= (b) ; i--) #define ld double #define ll long long using namespace std ; const int maxn = 5e5 + 10 ,s = 1000 , inf = 1e9 , mod = 998244353; int par[maxn] , r[maxn] , ma[maxn] , mark[maxn] , mb[maxn] ; ll dis[maxn] , a[maxn] , b[maxn] ; vector <pii> G[maxn] ; void dfs(int v){ for(auto[u,w] : G[v]){ if(u == par[v])continue ; par[u] = v; dfs(u) ;; } } void dist(int v, int p = -1){ for(auto [u,w] : G[v]){ if(u == p)continue ; dis[u ]= dis[v] + w ; dist(u , v); } } void dfs2(int v, int p =-1 ){ mark[v] =1 ; for(auto[u,w] : G[v]){ if(mark[u] == 1)continue ; r[u] = r[v]; dfs2(u ,v ); } } int max_score(int n, int x, int y, long long K,std::vector<int> U, std::vector<int> V, std::vector<int> W){ rep(i , 0 ,n)G[i].clear() ; rep(i , 0 , n-2){ G[V[i]].pb({U[i],W[i]}); G[U[i]].pb({V[i] , W[i]}) ; } dis[x] =0 ; dist(x); rep(i ,0, n-1){ a[i] = dis[i] ; } dis[y] = 0; dist(y) ; rep(i ,0 ,n-1){ b[i] = dis[i] ; } par[x] = -1 ; dfs(x) ; vector <int >vec ; int f = y ; while(f!=-1){ vec.pb(f); f = par[f] ; } rep(i , 0 , n)mark[i] =0 ; for(int x : vec)mark[x] =1 ; for(int x : vec){ r[x] = x ; dfs2(x) ; } reverse(all(vec)) ; int ans =0 ; rep(i , 0 ,n)ma[i] = mb[i] =0 ; rep(i , 0 ,sz(vec)-1){ ma[vec[i]] = 1; per(j , sz(vec)-1 , 0){ mb[vec[j]] =1 ; ll sm = K ; int ted= 0 ;; vector<ll> az; rep(k , 0 ,n-1){ if(r[k] == k){ ll mx = 0; if(ma[k] == 1){ted++;mx =max(mx , a[k]);} if(mb[k] == 1){ted++;mx =max(mx , b[k]);} sm -= mx ; }else{ if(ma[r[k]]==1)az.pb(a[k]); if(mb[r[k]]==1)az.pb(b[k]); } } if(sm < 0)continue ; sort(all(az)); rep(i , 0 ,sz(az)-1){ if(sm < az[i])break ; sm -= az[i] ; ted++ ; } ans = max(ans , ted) ; } rep(j ,0 , sz(vec)-1)mb[vec[j]] =0 ; } 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...