Submission #1103409

#TimeUsernameProblemLanguageResultExecution timeMemory
1103409aaaaaarrozNile (IOI24_nile)C++17
0 / 100
36 ms10756 KiB
#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 (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: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++){
      |             ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...