Recently, more and more illegal street races have been spotted at night in the city, and they have become a serious threat to public safety. Therefore, the Police Chief has decided to deploy speed cameras on the streets to collect evidence.
There are N+1 intersections in the city, connected by N roads. Every road has the same length of 1. A street race may take place between any two different intersections by using the roads connecting them. Limited by their budget, the police are able to deploy at most K speed cameras on these N roads. These K speed cameras should be installed such that the length of any possible street race route not covered by speed cameras should be as short as possible.
You are given a map of the city in the form of two arrays, A and B of length N, and an integer K:
- For each J (0 ≤ J < N) there is a road connecting intersections A[J] and B[J].
The Police Chief would like to know the minimum length of the longest path out of surveillance after placing at most K speed cameras.
Write a function:
int solution(vector<int> &A, vector<int> &B, int K);
that, given arrays A and B of N integers and integer K, returns the minimum length of the longest path unmonitored by speed cameras after placing at most K speed cameras.
For example, given K = 2 and the following arrays:
A[0] = 5 B[0] = 1 A[1] = 1 B[1] = 0 A[2] = 0 B[2] = 7 A[3] = 2 B[3] = 4 A[4] = 7 B[4] = 2 A[5] = 0 B[5] = 6 A[6] = 6 B[6] = 8 A[7] = 6 B[7] = 3 A[8] = 1 B[8] = 9the function should return 2. Two speed cameras can be installed on the roads between intersections 1 and 0 and between intersections 0 and 7. (Another solution would be to install speed cameras between intersections 0 and 7 and between intersections 0 and 6.) By installing speed cameras according the first plan, one of the longest paths without a speed camera starts at intersection 8, passes through intersection 6 and ends at intersection 3, which consists of two roads. (Other longest paths are composed of intersections 5, 1, 9 and 7, 2, 4).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..50,000];
- each element of arrays A and B is an integer within the range [0..N];
- K is an integer within the range [0..N];
- the distance between any two intersections is not greater than 900.
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const size_t N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (int i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (!Q.empty() && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
func.cpp: In function 'int solution(std::vector<int>&, std::vector<int>&, int)': func.cpp:10:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (N <= K) return 0; ^ func.cpp:22:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < N; i++) { ^ func.cpp:32:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < O.size(); i++) { ^ func.cpp:103:9: error: expected ';' before '}' token } ^
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (int i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (!Q.empty() && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
func.cpp: In function 'int solution(std::vector<int>&, std::vector<int>&, int)': func.cpp:32:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < O.size(); i++) { ^ func.cpp:103:9: error: expected ';' before '}' token } ^
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (!Q.empty() && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (Q.front() != root && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (Q.front() != root && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
[[3, 1, 0, 2, 4, 5, 5, 5, 5, 5, 21, 19, 7, 10, 11, 12, 6, 6, 8, 6, 14, 16, 17], [1, 0, 2, 4, 5, 19, 21, 7, 6, 16, 22, 20, 10, 11, 12, 13, 23, 8, 9, 14, 15, 17, 18], 3]
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (Q.front() != root && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
[[3, 1, 0, 2, 4, 5, 5, 5, 5, 5, 21, 19, 7, 10, 11, 12, 6, 6, 8, 6, 14, 16, 17], [1, 0, 2, 4, 5, 19, 21, 7, 6, 16, 22, 20, 10, 11, 12, 13, 23, 8, 9, 14, 15, 17, 18], 5]
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (Q.front() != root && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
[[3, 1, 0, 2, 4, 5, 5, 5, 5, 5, 21, 19, 7, 10, 11, 12, 6, 6, 8, 6, 14, 16, 17], [1, 0, 2, 4, 5, 19, 21, 7, 6, 16, 22, 20, 10, 11, 12, 13, 23, 8, 9, 14, 15, 17, 18], 5]
[],[],0
[0], [1], 1
function result: 4
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (Q.front() != root && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
[[3, 1, 0, 2, 4, 5, 5, 5, 5, 5, 21, 19, 7, 10, 11, 12, 6, 6, 8, 6, 14, 16, 17], [1, 0, 2, 4, 5, 19, 21, 7, 6, 16, 22, 20, 10, 11, 12, 13, 23, 8, 9, 14, 15, 17, 18], 5]
[[], [], 0]
[[0], [1], 1]
function result: 4
function result: 0
function result: 0
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (Q.front() != root && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
[[3, 1, 0, 2, 4, 5, 5, 5, 5, 5, 21, 19, 7, 10, 11, 12, 6, 6, 8, 6, 14, 16, 17], [1, 0, 2, 4, 5, 19, 21, 7, 6, 16, 22, 20, 10, 11, 12, 13, 23, 8, 9, 14, 15, 17, 18], 5]
[[0, 1], [1, 2], 1]
[[0], [1], 1]
function result: 4
function result: 1
function result: 0
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (Q.front() != root && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
[[3, 1, 0, 2, 4, 5, 5, 5, 5, 5, 21, 19, 7, 10, 11, 12, 6, 6, 8, 6, 14, 16, 17], [1, 0, 2, 4, 5, 19, 21, 7, 6, 16, 22, 20, 10, 11, 12, 13, 23, 8, 9, 14, 15, 17, 18], 5]
[[0, 1], [1, 2], 1]
[[0], [1], 1]
function result: 4
function result: 1
function result: 0
// you can use includes, for example:
#include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B, int K) {
const int N = A.size();
if (N <= K) return 0;
if (N < 3) return N-K;
vector<int> V(N+2,0);
vector<int> O(N+2,0);
vector<int> W(N+2,0);
vector<int> leafs;
vector<int> I(N+2,0);
queue<int> Q;
//read edges
for (int i = 0; i < N; i++) {
const int a = A[i] + 1;
const int b = B[i] + 1;
V[a]^=b;
V[b]^=a;
O[a]++;
O[b]++;
}
//find leafs
for (size_t i = 0; i < O.size(); i++) {
if (O[i] == 1) {
leafs.push_back(i);
Q.push(i);
}
}
//prepare tree structure
while(!Q.empty()) {
const int u = Q.front();
const int v = V[u];
Q.pop();
I[v]++;
V[v]^=u;
W[v] = W[u] + 1;
if (O[v] - I[v] == 1) Q.push(v);
}
const int root = V[0];
//do binary search
const int Lmax = W[root]*2;
int lower = 1;
int upper = Lmax;
int res = upper;
vector<int> D(N+2,0);
vector<int> L(Lmax+1);
queue<int> T;
fill(begin(I), end(I), 0);
fill(begin(W), end(W), 0);
while(lower <= upper) {
fill(begin(L), end(L), 0);
while (!Q.empty()) Q.pop();
while (!T.empty()) {
const int i = T.front();
W[i] = D[i] = I[i] = 0;
T.pop();
}
const int mid = (lower+upper)/2;
int k = K;
//try to construct a tree with maximal path no more than mid
for (int i : leafs) Q.push(i);
while (Q.front() != root && k >= 0) {
const int u = Q.front();
const int v = V[u];
Q.pop();
T.push(v);
if (W[v] + W[u] + 1 > mid) {
D[v]++;
--k;
W[v] = min(W[v], W[u] + 1);
} else {
I[v]++;
W[v]= max(W[v], W[u] + 1);
if (v == root) L[W[u] + 1]++;
}
if ( O[v] - I[v] - D[v] == 1 ) Q.push(v);
}
//count excessive edges around root
const int L0 = W[root];
while (k >= 0) {
int L1 = L0;
while (L1 > mid/2 && L[L1] <= 0) L1--;
L[L1]--;
int L2 = L1;
while (L2 > mid/2 && L[L2] <= 0) L2--;
L[L2]--;
if (L[L1] < 0 || L[L2] < 0 || L1 + L2 <= mid) break;
k--;
}
if (k >= 0) {
res = mid;
upper = mid - 1;
} else lower = mid + 1;
}
return res;
}
The solution obtained perfect score.