Submission #1230025

#TimeUsernameProblemLanguageResultExecution timeMemory
1230025the_coding_poohClosing Time (IOI23_closing)C++20
0 / 100
68 ms24744 KiB
#include "closing.h" #include <bits/stdc++.h> #define uwu return #define fs first #define sc second #define all(x) x.begin(), x.end() using namespace std; void output(vector <int> vec){ for(auto i:vec){ cerr << i << ' '; } cerr << '\n'; } const int SIZE = 2e5 + 5; vector <pair<int, long long>> graph[SIZE]; vector <long long> distA, distB; void get_dist(int nd, int pa, long long sum, bool ab){ if(ab) distA[nd] = sum; else distB[nd] = sum; for(auto i:graph[nd]){ if(i.fs == pa) continue; get_dist(i.fs, nd, sum + i.sc, ab); } uwu; } int id(long long x, vector <long long> &vec){ return lower_bound(all(vec), x) - vec.begin(); } long long BITree[SIZE]; void modify(int pos, long long md){ for(pos++; pos < SIZE; pos += pos & (-pos)){ BITree[pos] += md; } return; } long long prefix_sum(int pos){ long long ret = 0; for(pos++; pos; pos -= pos & (-pos)){ ret += BITree[pos]; } return ret; } int query_amnt(long long a, int N){ int L = -1, R = N - 1, M; while(L != R){ M = (L + R + 1) / 2; if(prefix_sum(M) <= a) L = M; else R = M - 1; } uwu L; } void init(int N){ distA.clear(), distB.clear(); for(int i = 0; i < N; i++){ graph[i].clear(); distA.push_back(0), distB.push_back(0); } for(int i = 0; i <= 2 * N; i++){ BITree[i] = 0; } return; } int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){ init(N); for(int i = 0; i < N - 1; i++){ graph[U[i]].push_back({V[i], W[i]}); graph[V[i]].push_back({U[i], W[i]}); } get_dist(X, -1, 0, 1); get_dist(Y, -1, 0, 0); vector <long long> mx, mn; for(int i = 0; i < N; i++){ mx.push_back(max(distA[i], distB[i])); mn.push_back(min(distA[i], distB[i])); } vector <long long> stmx = mx, stmn = mn; sort(all(stmx)); sort(all(stmn)); vector <pair<int, int>> op; for(int i = 0; i < N; i++){ op.push_back({id(mx[i], stmx), id(mn[i], stmn)}); modify(i, stmn[i]); } sort(all(op)); for(int i = 0; i < N; i++){ K -= stmn[i]; if(K < 0) return i; } return N; int ret = query_amnt(K, N) + 1; return ret; for(int i = 0; i < N; i++){ modify(op[i].sc, -stmn[op[i].sc]); K -= stmx[op[i].fs]; if(K < 0) break; ret = max(ret, i + query_amnt(K, N) + 2); output({i, ret}); } return ret; }
#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...