oj.uz

Submission #1109388

# Submission time Handle Problem Language Result Execution time Memory
1109388 2024-11-06T15:36:21 Z Ludissey Nile (IOI24_nile) C++17
6 / 100
 33 ms 10300 KB 
#include "nile.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

vector<int> parent;
vector<int> sz;
vector<int> mn;
int sm=0;

int getParent(int x){
  if(parent[x]==x) return x;
  return parent[x]=getParent(parent[x]);
}

void unite(int a, int b){
  a=getParent(a); b=getParent(b);
  if(a==b) return;
  parent[b]=a;
  if(sz[a]<sz[b]) swap(a,b);
  if(sz[a]%2) sm-=mn[a];
  if(sz[b]%2) sm-=mn[b];
  sz[a]+=sz[b];
  mn[a]=min(mn[a],mn[b]);
  if(sz[a]%2) sm+=mn[a];
}

std::vector<int> calculate_costs(std::vector<signed> W, std::vector<signed> A,  std::vector<signed> B, std::vector<signed> E) {
  int q = sz(E);
  int n=sz(W);
  mn.resize(n); sz.resize(n); parent.resize(n);
  vector<pair<int,int>> e(q);
  vector<pair<int,pair<int,int>>> a(n);
  for (int i = 0; i < q; i++) e[i]={E[i],i};
  for (int i = 0; i < n; i++) a[i]={W[i],{A[i],B[i]}};
  sort(all(a));
  sort(all(e));
  vector<pair<int,int>> df(n-1);
  for (int i = 0; i < n-1; i++) df[i]={a[i+1].first-a[i].first,i};
  sm=0;
  for (int i = 0; i < n; i++)
  {
    sm+=a[i].second.first;
    sz[i]=1;
    parent[i]=i;
    mn[i]=a[i].second.first-a[i].second.second;
  }
  sort(all(df));
  std::vector<int> R(q, 0);
  int j=0;
  for (int i = 0; i < q; i++)
  {
    while(j<n-1){
      if(df[j].first>e[i].first) break;
      unite(df[j].second,df[j].second+1);
      j++;
    }
    R[e[i].second]=sm;
  }
  
  return R;
}

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 2 ms 592 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 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 30 ms 9032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9028 KB Output is correct
2 Incorrect 33 ms 10300 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 2 ms 592 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 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 592 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 504 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Incorrect 30 ms 9032 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9028 KB Output is correct
2 Incorrect 33 ms 10300 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 2 ms 592 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Incorrect 30 ms 9032 KB Output isn't correct
9 Halted 0 ms 0 KB -