oj.uz

Submission #1103409

# Submission time Handle Problem Language Result Execution time Memory
1103409 2024-10-20T23:41:35 Z aaaaaarroz Nile (IOI24_nile) C++17
0 / 100
 36 ms 10756 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Dsu {
	ll cnt;
    vector<ll> parent, rank, size;
    Dsu(ll N) {
		cnt=2*N;
        parent.resize(N);
        rank.resize(N);
        size.resize(N, 1);
        for (ll i = 0; i < N; i++){
            parent[i] = i;
        }
    }
    bool isSameSet(ll i, ll j){
        return findSet(i) == findSet(j);
    }
    ll findSet(ll i) { 
        if(parent[i] == i){
            return i;
        }else{
            return parent[i] = findSet(parent[i]);
        } 
    }
    void unionSet(ll i, ll j){
        ll x = findSet(i);
        ll y = findSet(j);
        if (x != y){
			if(getSize(i)==getSize(j)&&getSize(i)%2==1){
				cnt-=2;
			}
            if (rank[x] > rank[y]){
                parent[y] = x;
                size[x] += size[y];
            }else if(rank[x] < rank[y]){
                parent[x] = y;
                size[y] += size[x];
            }else{
                parent[x] = y;
                size[y] += size[x];
                rank[y]++;
            }
        }
    }
    ll getSize(ll i){
        return size[findSet(i)];
    }
	ll res(){
		return cnt;
	}
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {                   
	sort(W.begin(),W.end());
	ll n=W.size();
	Dsu dsu(n);
	vector<vector<ll>>edges;
	for(ll i=0;i<n-1;i++){
		edges.push_back({W[i+1]-W[i],i,i+1});
	}
	edges.push_back({2000000020,-1,-1});
    sort(edges.begin(),edges.end());
	vector<pair<ll,ll>>q;
	for(ll i=0;i<E.size();i++){
		q.push_back({E[i],i});
	}
    sort(q.begin(),q.end());
	vector<ll>queries(E.size());
	ll puntero=0;
	for(auto[d,pos]:q){
		while(edges[puntero][0]<=d&&puntero<n){
			ll u=edges[puntero][1],v=edges[puntero][2];
			if(!dsu.isSameSet(u, v)){
				dsu.unionSet(u, v);
			}
			puntero++;
		}
		queries[pos]=dsu.res();
	}
	return queries;
}

Compilation message

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:64:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(ll i=0;i<E.size();i++){
      |             ~^~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 10756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 10668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 10668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -