Submission #1228696

#TimeUsernameProblemLanguageResultExecution timeMemory
1228696CELD_07봉쇄 시간 (IOI23_closing)C++20
8 / 100
90 ms31164 KiB
#include "closing.h" #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> typedef long long ll; typedef long double ld; #define endl "\n" #define vll vector<ll> #define sd second #define ft first #define all(x) x.begin(),x.end() #define allr(x) x.rbegin(),x.rend() #define pll pair<ll, ll> #define mod 1000000007 #define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> #define inf (ll)1e15 #define db(x) cout<<#x<<" : "<<x<<endl; #define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x); using namespace std; using namespace __gnu_pbds; ll dx[]={1, -1, 0, 0}; ll dy[]={0, 0, 1, -1}; inline ll sm(ll a, ll b){ return ((a%mod)+(b%mod))%mod; } inline ll ml(ll a, ll b){ return ((a%mod)*(b%mod))%mod; } inline ll rs(ll a, ll b){ return ((a%mod)-(b%mod)+mod)%mod; } ll bpow(ll a , ll b) { if (b==0)return 1; if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod; ll r=bpow (a ,b/ 2) ; return ((r%mod)*(r%mod))%mod; } vector<vector<pair<ll, ll>>> adj; inline void dfs(vector<ll>& dist, ll n, ll p){ for(auto& [x, y]: adj[n]){ if(x==p)continue; dist[x]=dist[n]+y; dfs(dist, x, n); } } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){ if(X>Y)swap(X, Y); vector<ll> dist(N+1, 0), dist1(N+1, 0); vector<vector<pair<ll, ll>>>().swap(adj); adj.resize(N+1); for(int i=0; i<N-1; i++){ adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } dfs(dist, X, X); dfs(dist1, Y, Y); vector<ll> v2; for(int i=0; i<N; i++){ v2.push_back(min(dist[i], dist1[i])); } sort(all(v2)); ll cnt=0, res=0; for(int i=0; i<N; i++){ cnt+=v2[i]; if(cnt<=K)res=i+1; } return res; }
#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...