oj.uz

Submission #1112258

# Submission time Handle Problem Language Result Execution time Memory
1112258 2024-11-13T22:25:12 Z FIFI_cpp Nile (IOI24_nile) C++17
38 / 100
 72 ms 14592 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>

#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppi pair<int,pair<int,int>>
#define int long long
#define ll long long

using namespace std;
//    /\_/\
//   (= ._.)
//   / >  \>
// encouraging cat
const int INF = 10000000000000000;
const int mod = 1000000007;
//const int mod = 998244353;
const int MAXN = 200005;
//ifstream fin('xor.in');
//ofstream fout('xor.out');
ll curr_res = 0;

struct Index {
    ll a,b,w;
};
struct Node {
    ll parent, min_value, min_index, size, sb;
};
vector<Index> vals;
vector<Node> info;
vector<pair<ll,ll>> e;
bool cmp(const Index &x, const Index &y) { return x.w < y.w; }
ll find_parent(ll x)
{
    if (x == info[x].parent)
    {
        return x;
    }
    return info[x].parent = find_parent(info[x].parent);
}
void remove(Node x)
{
    if (x.size % 2 == 0)
    {
        curr_res -= x.sb;
    }
    else
    {
        curr_res -= x.sb - vals[x.min_index].b + vals[x.min_index].a;
    }
}
void add(Node x)
{
    if (x.size % 2 == 0)
    {
        curr_res += x.sb;
    }
    else
    {
        curr_res += x.sb - vals[x.min_index].b + vals[x.min_index].a;
    }
}
pair<Node, Node> merge(Node x,Node y, ll ix, ll iy)
{
    y.parent = ix;
    x.size += y.size;
    if (y.min_value < x.min_value)
    {
        x.min_value = y.min_value;
        x.min_index = y.min_index;
    }
    x.sb += y.sb;
    return {x,y};
}
void onion (ll x, ll y)
{
    x = find_parent(x);
    y = find_parent(y);
    if (x == y)
        return ;
    remove(info[x]);
    remove(info[y]);
    if (info[y].size > info[x].size)
    {
        swap(x,y);
    }
    pair<Node, Node> m = merge(info[x], info[y], x, y);
    info[x] = m.first;
    info[y] = m.second;
    add(info[x]);
}
#undef int long long
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
    ll n = A.size();
    info.resize(n);
    vals.resize(n);
    for (ll i = 0;i < n;i++)
    {
        vals[i].a = A[i];
        vals[i].b = B[i];
        vals[i].w = W[i];
    }
    sort(all(vals), cmp);
    for (ll i = 0;i < n;i++)
    {
        info[i].parent = i;
        info[i].min_index = i;
        info[i].min_value = vals[i].a - vals[i].b;
        info[i].sb = vals[i].b;
        info[i].size = 1;
        curr_res += vals[i].a;
    }
    ll q = E.size();
    e.resize(q);
    for (ll i = 0;i < q;i++)
    {
        e[i].first = E[i];
        e[i].second = i;
    }
    sort(all(e));
    vector<pair<ll,ll>> diff; // 
    for (ll i = 0;i < n - 1;i++)
    {
        diff.push_back({vals[i + 1].w - vals[i].w, i});
    }
    sort(all(diff));
    vector<ll> res(q);
    ll e_index = 0;
    for (ll i = 0;i < diff.size();i++)
    {
        if (diff[i].first <= e[e_index].first)
        {
            ll a = diff[i].second;
            ll b = diff[i].second + 1;
            onion(a,b);
        }
        else
        {
            res[e[e_index].second] = curr_res;
            e_index++;
            i--;
        }
    }
    for (; e_index < q;e_index++)
    {
        res[e[e_index].second] = curr_res;
    }
    return res;
}

Compilation message

nile.cpp:33:1: warning: multi-line comment [-Wcomment]
   33 | //    /\_/\
      | ^
nile.cpp:114:12: warning: extra tokens at end of #undef directive
  114 | #undef int long long
      |            ^~~~
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:152:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for (ll i = 0;i < diff.size();i++)
      |                   ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 12096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12228 KB Output is correct
2 Correct 31 ms 12116 KB Output is correct
3 Correct 38 ms 12228 KB Output is correct
4 Correct 36 ms 12240 KB Output is correct
5 Correct 37 ms 12224 KB Output is correct
6 Correct 45 ms 12228 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Incorrect 1 ms 760 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Incorrect 31 ms 12096 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12228 KB Output is correct
2 Correct 31 ms 12116 KB Output is correct
3 Correct 38 ms 12228 KB Output is correct
4 Correct 36 ms 12240 KB Output is correct
5 Correct 37 ms 12224 KB Output is correct
6 Correct 45 ms 12228 KB Output is correct
7 Correct 61 ms 14592 KB Output is correct
8 Correct 54 ms 14524 KB Output is correct
9 Correct 64 ms 14524 KB Output is correct
10 Correct 72 ms 14524 KB Output is correct
11 Correct 57 ms 14464 KB Output is correct
12 Correct 57 ms 14528 KB Output is correct
13 Correct 57 ms 14524 KB Output is correct
14 Correct 55 ms 14524 KB Output is correct
15 Correct 70 ms 14524 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Incorrect 31 ms 12096 KB Output isn't correct
9 Halted 0 ms 0 KB -