oj.uz

Submission #1102795

# Submission time Handle Problem Language Result Execution time Memory
1102795 2024-10-18T23:46:46 Z PedroBigMan Nile (IOI24_nile) C++17
38 / 100
 70 ms 16316 KB 
#include "nile.h"
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

vector<ll> extra;

class DSU //with range compression and union by subtree size
{
    public:
    ll N;
    vector<ll> p,siz; 
    vector<ll> min_value;
    
    DSU(ll n)
    {
        N=n; REP(i,0,N) {p.pb(i); siz.pb(1); min_value.pb(extra[i]);}
    }
    
    ll find(ll x)
    {
        if(p[x]==x) {return x;}
        ll ans=find(p[x]);
        p[x]=ans; 
        return ans;
    }
    
    void unionn(ll a, ll b)
    {
        a=find(a); b=find(b);
		if(a==b) {return;}
        if(siz[a]>siz[b]) {swap(a,b);}
        p[a]=b; siz[b]+=siz[a]; 
        min_value[b]=min(min_value[a],min_value[b]);
    }
	
	vector<vector<ll> > EquivalenceClasses() //O(N)
	{
		vector<vector<ll> > rep; REP(i,0,N) {rep.pb({});}
		REP(i,0,N) {rep[find(i)].pb(i);}
		vector<vector<ll> > CC; 
		REP(i,0,N) {if(rep[i].size()>0) {CC.pb(rep[i]);}}
		return CC;
	}
};



vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) 
{
  ll Q = E.size(); ll N = A.size();
  vector<pl> a; 
  ll basis = 0LL; REP(i,0,N) {basis+=B[i]; a.pb({W[i],A[i]-B[i]});}
  sort(whole(a)); REP(i,0,N) {extra.pb(a[i].ss);}
  DSU X(N);
  vector<ll> ans(Q,0); vector<pl> queries; REP(q,0,Q) {queries.pb({E[q],q});}
  sort(whole(queries)); ll D, ind;
  vector<pl> dist; REP(i,0,N-1) {dist.pb({a[i+1].ff-a[i].ff,i});} sort(whole(dist));
  ll dist_ind = 0; ll unite;
  ll curans = 0; REP(i,0,N) {curans+=extra[i];}
  ll old_extra, new_extra;
  ll J, K;
  REP(q,0,Q)
  {
    D = queries[q].ff; ind = queries[q].ss;
    while(dist_ind<N-1 && dist[dist_ind].ff<=D)
    {
        unite = dist[dist_ind].ss;
        J = X.find(unite); K = X.find(unite+1);
        old_extra = 0;
        if(X.siz[J]%2!=0) {old_extra+=X.min_value[J];}
        if(X.siz[K]%2!=0) {old_extra+=X.min_value[K];}
        X.unionn(J,K); J = X.find(J);
        new_extra=0;
        if(X.siz[J]%2!=0) {new_extra=X.min_value[J];}
        curans += (new_extra-old_extra);
        dist_ind++;
    }
    ans[ind]=curans+basis;
  } 
  return ans;
}

Compilation message

nile.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
nile.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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 760 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 648 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 456 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 12952 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 34 ms 12992 KB Output is correct
2 Correct 34 ms 12984 KB Output is correct
3 Correct 40 ms 12868 KB Output is correct
4 Correct 42 ms 12988 KB Output is correct
5 Correct 40 ms 12984 KB Output is correct
6 Correct 45 ms 12988 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 648 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 456 KB Output is correct
7 Incorrect 2 ms 760 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 760 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 648 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 456 KB Output is correct
7 Incorrect 34 ms 12952 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 34 ms 12992 KB Output is correct
2 Correct 34 ms 12984 KB Output is correct
3 Correct 40 ms 12868 KB Output is correct
4 Correct 42 ms 12988 KB Output is correct
5 Correct 40 ms 12984 KB Output is correct
6 Correct 45 ms 12988 KB Output is correct
7 Correct 56 ms 16312 KB Output is correct
8 Correct 58 ms 16312 KB Output is correct
9 Correct 63 ms 16312 KB Output is correct
10 Correct 64 ms 16192 KB Output is correct
11 Correct 63 ms 16312 KB Output is correct
12 Correct 65 ms 16312 KB Output is correct
13 Correct 60 ms 16316 KB Output is correct
14 Correct 61 ms 16312 KB Output is correct
15 Correct 70 ms 16312 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 760 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 648 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Incorrect 34 ms 12952 KB Output isn't correct
9 Halted 0 ms 0 KB -