oj.uz

Submission #1112256

# Submission time Handle Problem Language Result Execution time Memory
1112256 2024-11-13T22:18:17 Z FIFI_cpp Nile (IOI24_nile) C++17
38 / 100
 92 ms 16488 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<int,int>> e;
bool cmp(const Index &x, const Index &y) { return x.w < y.w; }
int find_parent(int 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, int ix, int 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 (int x, int 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)
{
    int n = A.size();
    info.resize(n);
    vals.resize(n);
    for (int 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 (int 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;
    }
    int q = E.size();
    e.resize(q);
    for (int i = 0;i < q;i++)
    {
        e[i].first = E[i];
        e[i].second = i;
    }
    sort(all(e));
    vector<pair<ll,ll>> diff; // 
    for (int i = 0;i < n - 1;i++)
    {
        diff.push_back({vals[i + 1].w - vals[i].w, i});
    }
    sort(all(diff));
    vector<ll> res(q);
    int e_index = 0;
    for (int i = 0;i < diff.size();i++)
    {
        if (diff[i].first <= e[e_index].first)
        {
            int a = diff[i].second;
            int 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:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for (int 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 764 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 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 2 ms 592 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 12228 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 33 ms 12224 KB Output is correct
2 Correct 36 ms 13612 KB Output is correct
3 Correct 42 ms 13500 KB Output is correct
4 Correct 39 ms 13488 KB Output is correct
5 Correct 45 ms 13612 KB Output is correct
6 Correct 46 ms 13608 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 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 2 ms 592 KB Output is correct
7 Incorrect 2 ms 592 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 764 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 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 2 ms 592 KB Output is correct
7 Incorrect 32 ms 12228 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 33 ms 12224 KB Output is correct
2 Correct 36 ms 13612 KB Output is correct
3 Correct 42 ms 13500 KB Output is correct
4 Correct 39 ms 13488 KB Output is correct
5 Correct 45 ms 13612 KB Output is correct
6 Correct 46 ms 13608 KB Output is correct
7 Correct 68 ms 16048 KB Output is correct
8 Correct 55 ms 16316 KB Output is correct
9 Correct 65 ms 16484 KB Output is correct
10 Correct 61 ms 16432 KB Output is correct
11 Correct 61 ms 16488 KB Output is correct
12 Correct 59 ms 16328 KB Output is correct
13 Correct 61 ms 16316 KB Output is correct
14 Correct 67 ms 16260 KB Output is correct
15 Correct 92 ms 16316 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 764 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 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 2 ms 592 KB Output is correct
8 Incorrect 32 ms 12228 KB Output isn't correct
9 Halted 0 ms 0 KB -