oj.uz

Submission #1103405

# Submission time Handle Problem Language Result Execution time Memory
1103405 2024-10-20T23:31:33 Z aaaaaarroz Nile (IOI24_nile) C++17
0 / 100
 36 ms 9488 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Dsu {
	int cnt;
    vector<int> parent, rank, size;
    Dsu(int N) {
		cnt=2*N;
        parent.resize(N);
        rank.resize(N);
        size.resize(N, 1);
        for (int i = 0; i < N; i++){
            parent[i] = i;
        }
    }
    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }
    int findSet(int i) { 
        if(parent[i] == i){
            return i;
        }else{
            return parent[i] = findSet(parent[i]);
        } 
    }
    void unionSet(int i, int j){
        int x = findSet(i);
        int 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]++;
            }
        }
    }
    int getSize(int i){
        return size[findSet(i)];
    }
	int res(){
		return cnt;
	}
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {                   
	sort(W.begin(),W.end());
	int n=W.size();
	Dsu dsu(n);
	vector<vector<int>>edges;
	for(int i=0;i<n-1;i++){
		edges.push_back({W[i+1]-W[i],i,i+1});
	}
	sort(edges.begin(),edges.end());
	edges.push_back({2000000001,-1,-1});
	vector<pair<ll,ll>>q;
	for(int i=0;i<E.size();i++){
		q.push_back({E[i],i});
	}
    sort(q.begin(),q.end());
	vector<ll>queries(E.size());
	int puntero=0;
	for(auto[d,pos]:q){
		while(edges[puntero][0]<=d){
			int 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:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int 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 9460 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 33 ms 9488 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 33 ms 9488 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 -