oj.uz

Submission #1102796

# Submission time Handle Problem Language Result Execution time Memory
1102796 2024-10-18T23:47:54 Z PedroBigMan Nile (IOI24_nile) C++17
38 / 100
 67 ms 16320 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 = 0LL; 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 = 0LL;
        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=0LL;
        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 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 768 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 12980 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 31 ms 12992 KB Output is correct
2 Correct 32 ms 12992 KB Output is correct
3 Correct 38 ms 12992 KB Output is correct
4 Correct 38 ms 12984 KB Output is correct
5 Correct 39 ms 12984 KB Output is correct
6 Correct 43 ms 12912 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Incorrect 2 ms 764 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 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Incorrect 33 ms 12980 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 31 ms 12992 KB Output is correct
2 Correct 32 ms 12992 KB Output is correct
3 Correct 38 ms 12992 KB Output is correct
4 Correct 38 ms 12984 KB Output is correct
5 Correct 39 ms 12984 KB Output is correct
6 Correct 43 ms 12912 KB Output is correct
7 Correct 55 ms 16312 KB Output is correct
8 Correct 59 ms 16320 KB Output is correct
9 Correct 61 ms 16320 KB Output is correct
10 Correct 59 ms 16312 KB Output is correct
11 Correct 61 ms 16312 KB Output is correct
12 Correct 64 ms 16316 KB Output is correct
13 Correct 64 ms 16304 KB Output is correct
14 Correct 61 ms 16320 KB Output is correct
15 Correct 67 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 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Incorrect 33 ms 12980 KB Output isn't correct
9 Halted 0 ms 0 KB -