Submission #1099758

#TimeUsernameProblemLanguageResultExecution timeMemory
1099758model_codeNile (IOI24_nile)C++17
38 / 100
89 ms14408 KiB
// incorrect/anany_wa_always_min_only_adjacent.cpp #include "nile.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() using ll = long long; using ii = pair<int, int>; const int N = 2e5 + 5; int par[N]; int mn[N]; int sz[N]; /* Idea if the cc size is even I get all of them if it's odd I get all of them except one that one is the one with minimal A[i] - B[i] */ int get(int i){return i == par[i] ? i : par[i] = get(par[i]);} vector<long long>calculate_costs(vector<int>W, vector<int>A, vector<int>B, vector<int>E) { int n = A.size(); int m = E.size(); ///Get elements sorted in order of Weight vector<ii > queries; vector<ii > weights; ll cost = 0; for(int i = 0; i < m; i++) { queries.push_back(ii(E[i], i)); } for(int i = 0; i < n; i++) { weights.push_back(ii(W[i], i)); par[i] = i; mn[i] = A[i] - B[i]; sz[i] = 1; cost += A[i]; } sort(all(queries)); sort(all(weights)); vector<ll> ans(m); set<pair<int, ii> > edges; for(int i = 1; i < n; i++) { edges.insert(make_pair(weights[i].first-weights[i-1].first,ii(weights[i-1].second, weights[i].second))); //INCORRECT: must consider (i,i+2) as well } for(auto p : queries) { while(edges.size() && edges.begin()->first <= p.first) { int u = edges.begin()->second.first, v = edges.begin()->second.second; edges.erase(edges.begin()); u = get(u); v = get(v); if(u != v) { if(sz[u] & 1) cost -= mn[u]; if(sz[v] & 1) cost -= mn[v]; sz[u] += sz[v]; mn[u] = min(mn[u], mn[v]); //INCORRECT: always return min par[v] = u; if(sz[u] & 1) cost += mn[u]; } } ans[p.second] = cost; } 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...