oj.uz

Submission #1112257

# Submission time Handle Problem Language Result Execution time Memory
1112257 2024-11-13T22:21:10 Z FIFI_cpp Nile (IOI24_nile) C++17
38 / 100
 69 ms 14536 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; }
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)
        {
            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: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 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 2 ms 768 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 31 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 32 ms 12240 KB Output is correct
2 Correct 39 ms 12220 KB Output is correct
3 Correct 41 ms 12240 KB Output is correct
4 Correct 40 ms 12220 KB Output is correct
5 Correct 46 ms 12028 KB Output is correct
6 Correct 41 ms 12224 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 604 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 2 ms 768 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 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Incorrect 31 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 32 ms 12240 KB Output is correct
2 Correct 39 ms 12220 KB Output is correct
3 Correct 41 ms 12240 KB Output is correct
4 Correct 40 ms 12220 KB Output is correct
5 Correct 46 ms 12028 KB Output is correct
6 Correct 41 ms 12224 KB Output is correct
7 Correct 57 ms 14524 KB Output is correct
8 Correct 55 ms 14524 KB Output is correct
9 Correct 64 ms 14524 KB Output is correct
10 Correct 69 ms 14524 KB Output is correct
11 Correct 61 ms 14536 KB Output is correct
12 Correct 63 ms 14536 KB Output is correct
13 Correct 58 ms 14524 KB Output is correct
14 Correct 56 ms 14536 KB Output is correct
15 Correct 62 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 604 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Incorrect 31 ms 12228 KB Output isn't correct
9 Halted 0 ms 0 KB -