Submission #1068192

#TimeUsernameProblemLanguageResultExecution timeMemory
1068192jamjanekClosing Time (IOI23_closing)C++17
9 / 100
1042 ms30916 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; bool odw[200010],odw2[200010]; long long dist[200010]; vector<pair<int,long long>>graf[200010]; long long odl[200010], odl2[200010]; void dfs(int x, int o){ for(auto j: graf[x]) if(j.first!=o){ odl[j.first]=odl[x]+j.second; dfs(j.first, x); } } void dfs2(int x, int o){ for(auto j: graf[x]) if(j.first!=o){ odl2[j.first]=odl2[x]+j.second; dfs2(j.first, x); } } int max_score(int n, int x, int y, long long K,vector<int> U, vector<int> V, vector<int> W) { int i; priority_queue<pair<long long,int>>kolejka,kolejka2; for(i=0;i<n;i++){ graf[i].clear(); } for(i=0;i<n-1;i++){ graf[U[i]].push_back({V[i], W[i]}); graf[V[i]].push_back({U[i], W[i]}); } odl[y] = 0; odl2[x] = 0; dfs(y, -1); dfs2(x, -1); int wynik = 0; for(int ile_x=0;ile_x<n;ile_x++){ long long k=K; for(i=0;i<n;i++)odw[i]=odw2[i]=0,dist[i]=0; while(kolejka.size())kolejka.pop(); while(kolejka2.size())kolejka2.pop(); kolejka.push({0,x}); int wyn=0; while(kolejka.size()){ if(wyn==ile_x)break; auto a = kolejka.top(); kolejka.pop(); if(odw[a.second])continue; if(-a.first>k)break; dist[a.second]=-a.first; odw[a.second]=1; k+=a.first; wyn++; for(auto j: graf[a.second]) if(odw[j.first]==0) kolejka.push({-odl2[j.first], j.first}); } kolejka2.push({0,y}); while(kolejka2.size()){ auto a = kolejka2.top(); kolejka2.pop(); if(-a.first>k)break; dist[a.second]+=-a.first; odw2[a.second]=1; k+=a.first; wyn++; for(auto j: graf[a.second]) if(odw2[j.first]==0) kolejka2.push({-max(0ll, odl[j.first]-dist[j.first]), j.first}); } while(kolejka.size()){ auto a = kolejka.top(); kolejka.pop(); if(odl2[a.second]<=dist[a.second]){ odw[a.second]=1; wyn++; for(auto j: graf[a.second]) if(!odw[j.first]) kolejka.push({0,j.first}); } } // printf("%d %d\n", ile_x, wyn); // for(i=0;i<n;i++)printf("%d ", odw[i]);printf("\n"); // for(i=0;i<n;i++)printf("%d ", odw2[i]);printf("\n"); wynik = max(wyn,wynik); } return wynik; }
#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...