Submission #1103405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103405		aaaaaarroz	Nile (IOI24_nile)	C++17	0 / 100	36 ms	9488 KiB

nile

#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 (stderr)

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
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18