Submission #1245498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245498		CyberCow	Nile (IOI24_nile)	C++20	0 / 100	26 ms	6336 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[100005];
int p[100005];
int sz[100005];

void make_set(int i)
{
  p[i]  =i;
  sz[i] = 1;
}

int get_papa(int i)
{
  if(p[i] == i)
  return i;
  return p[i] = get_papa(p[i]);
}

int ans = 0;

void union_set(int a, int b)
{
  a = get_papa(a);
  b = get_papa(b);
  if(a == b)return;
  if(sz[a] > sz[b])swap(a, b);
  if(sz[a] % 2 && sz[b] % 2)
  ans++;
  p[a] = b;
  sz[b]+= a;
}

vector<long long> calculate_costs(vector<int> W, vector<int> A,
                                      vector<int> B, vector<int> E) {
  int Q = (int)E.size();
  vector<long long> R;
  vector<pair<int, pair<int, int>>> qaq;
  for (int i = 0; i < A.size(); i++)
  {
    qaq.push_back({W[i], {A[i], B[i]}});
  }
  sort(qaq.begin(), qaq.end());
  for (int i = 0; i < A.size(); i++)
  {
    W[i] = qaq[i].first;
    A[i] = qaq[i].second.first;
    B[i] = qaq[i].second.second;
    make_set(i);
  }
  vector<pair<int ,int>> zuyg;
  for (int i = 0; i < W.size() - 1; i++)
  {
    zuyg.push_back({W[i + 1] - W[i], i});
  }
  sort(zuyg.begin(), zuyg.end());
  vector<pair<int, int>> sq;
  for (int i = 0; i < E.size(); i++)
  {
    sq.push_back({E[i], i});
  }
  sort(sq.begin(), sq.end());
  int ind = 0;
  vector<pair<int, int>> hogna;
  for(auto g: sq)
  {
    while (ind < zuyg.size() && zuyg[ind].first <= g.first)
    {
      union_set(zuyg[ind].second, zuyg[ind].second + 1);
      ind++;
    }
    hogna.push_back({g.second, 2 * (A.size() - ans)});
  }
  sort(hogna.begin(), hogna.end());
  for (int i = 0; i < hogna.size(); i++)
  {
    R.push_back(hogna[i].second);
  }
  return R;  
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18