제출 #1239389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239389		walizamanee	나일강 (IOI24_nile)	C++20	38 / 100	57 ms	8384 KiB

nile

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

vector<pair<int , int>> arr , e;
vector<pair<int , pair<int , int>>> w;
int n , q , par[1000001] , choto[1000001] , koita[1000001] , ek , dui;
long long sum , one , two , uttor ;

int findpar( int me ) {
    if( par[me] == me ) return me;
    else{
       par[me] = findpar( par[me] );
       return par[me];
    }
}

void comb( int a , int b ) {
    int aa = findpar( a );
    int bb = findpar( b );
    if( koita[aa] < koita[bb] ) swap( aa , bb );
    if( (koita[aa] % 2) == 1 ) {
       uttor -= (ll)choto[aa];
    }
    if( (koita[bb] % 2) == 1 ) {
       uttor -= (ll)choto[bb];
    }
    par[bb] = aa;
    koita[aa] += koita[bb];
    choto[aa] = min( choto[aa] , choto[bb] );
    if( koita[aa] % 2 == 1 ) {
      uttor += (ll)choto[aa];
    }
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  n = (int)W.size();
  q = (int)E.size();
  w.clear();
  e.clear();
  for( int z = 0; z < n; z++ ){
     w.push_back({W[z] , {A[z] , B[z]}});
  }
  for( int z = 0; z < q; z++ ){
     e.push_back({E[z] , z});
  }
  sort( e.begin() , e.end() );
  sort( w.begin() , w.end() );
  arr.clear();
  for( int z = 1; z < n; z++ ) {
    arr.push_back({w[z].first - w[z - 1].first , (z - 1) });
  }                                  
  sort( arr.begin() , arr.end() );
  sum = 0;
  uttor = 0;
  for( int z = 0; z < n; z++ ) {
     sum += (long long)w[z].second.second;
     choto[z] = w[z].second.first - w[z].second.second;
     par[z] = z;
     koita[z] = 1;
     uttor += (ll)w[z].second.first;
  }
  int here = 0;
  vector<long long> ans(q);
 
  for( int z = 0; z < q; z++ ) {
     while( here < n - 1 && e[z].first >= arr[here].first ) {
         comb( arr[here].second , arr[here].second + 1 );
         here++;
     }
     ans[e[z].second] = uttor;
    /* for( int z = 0; z < n; z++ ) {
        cerr << choto[z] << " ";
     }
     cerr << "\n";
     */
  }

  return ans;
}

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