Submission #1109930

#TimeUsernameProblemLanguageResultExecution timeMemory
1109930KasymKNile (IOI24_nile)C++17
0 / 100
38 ms6084 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define all(v) v.begin(), v.end() #define ll long long #define pb push_back #define pii pair<int, int> #define pli pair<ll, int> #define pll pair<ll, ll> #define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i) #define wr puts("----------------") template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} const int N = 1e5+5; int rep[N], sz[N], n, answer; void init(){ for(int i = 0; i < n; ++i) rep[i] = i, sz[i] = 1; answer = 2*n; } int find(int x){ if(rep[x]==x) return x; return rep[x]=find(rep[x]); } void merge(int a, int b){ a = find(a), b = find(b); if(sz[a]<sz[b]) swap(a, b); sz[a] += sz[b]; rep[b] = a; if(sz[a]&1 and sz[b]&1) answer -= 2; } vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){ n = (int)W.size(); vector<pii> v; for(int i = 0; i < n; ++i) v.pb({W[i], i}); sort(all(v)); vector<array<int, 3>> as; for(int i = 1; i < n; ++i) as.pb({v[i].ff-v[i-1].ff, v[i].ss, v[i-1].ss}); sort(all(as)); init(); vector<pii> Q; for(int i = 0; i < (int)E.size(); ++i) Q.pb({E[i], i}); vector<ll> ans((int)Q.size()); int ii = 0; for(auto &d : Q){ while(ii<(int)as.size() and as[ii][0]<=d.ff) merge(as[ii][1], as[ii][2]), ii++; ans[d.ss] = answer; } return ans; }
#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...