| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1109891 |
2024-11-08T02:51:14 Z |
Trisanu_Das |
Nile (IOI24_nile) |
C++17 |
|
64 ms |
12540 KB |
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
const int N = 3e5 + 5;
int par[N];
int sbtr[N];
int H;
void init(int n) {
H = 2 * n;
for (int i = 0; i < n; i++) {
par[i] = i;
sbtr[i] = 1;
}
}
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return;
if (sbtr[py] > sbtr[px]) swap(px, py);
int a = sbtr[px], b = sbtr[py];
sbtr[px] += sbtr[py];
par[py] = px;
if (a % 2 == 1 && b % 2 == 1) H -= 2;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size();
init(n);
int q = E.size();
if (q <= 5) {
vector<ll> ans;
vector<pair<ll, ll>> v;
for (int i = 0; i < n; i++) {
v.pb({W[i], i});
}
sort(v.begin(), v.end());
for (int f = 0; f < q; f++) {
ll d = E[f];
vector<vector<ll>> dp(n + 5, vector<ll>(2, 1e17));
for (int i = 0; i < n; i++) {
int a = v[i].ss;
int b = i > 0 ? v[i - 1].ss : -1;
int c = i > 1 ? v[i - 2].ss : -1;
if (i > 0 && abs(W[a] - W[b]) <= d) {
dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] - A[b] + B[b] + B[a]);
}
if (i > 1 && abs(W[a] - W[c]) <= d) {
dp[i + 1][1] = min(dp[i + 1][1], dp[i - 1][0] - A[c] + B[c] + B[a] + A[b]);
}
dp[i + 1][0] = min(dp[i + 1][0], min(dp[i][1], dp[i][0]) + A[a]);
}
ans.pb(min(dp[n][0], dp[n][1]));
}
return ans;
}
vector<ll> ans(q);
vector<pair<ll, ll>> v;
vector<pair<ll, pair<int, int>>> vc;
for (int i = 0; i < n; i++) {
v.pb({W[i], i});
}
sort(v.begin(), v.end());
for (int i = 1; i < n; i++) {
int x = abs(v[i].ff - v[i - 1].ff);
int a = v[i - 1].ss, b = v[i].ss;
vc.pb({x, {a, b}});
}
sort(vc.begin(), vc.end());
int idx = 0;
vector<pair<int, int>> vec;
for (int i = 0; i < q; i++) {
vec.pb({E[i], i});
}
sort(vec.begin(), vec.end());
for (int f = 0; f < q; f++) {
ll d = vec[f].ff;
int k = vec[f].ss;
while (idx < vc.size() && vc[idx].ff <= d) {
int a = vc[idx].ss.ff, b = vc[idx].ss.ss;
unite(a, b);
idx++;
}
ans[k] = H;
}
return ans;
}
Compilation message
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while (idx < vc.size() && vc[idx].ff <= d) {
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
12540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
12540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
12540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
