제출 #1248232

#제출 시각아이디문제언어결과실행 시간메모리
1248232meisgood나일강 (IOI24_nile)C++20
32 / 100
56 ms8508 KiB
#include <bits/stdc++.h> using namespace std ; // #define test #ifndef test #include "nile.h" #endif //////////////////////////////////////////////////////////////////////// int gp[100003] ; int gpmn[100003] ; int gpsz[100003] ; int tt=0 ; int dsu(int x){ if (x==gp[x]) return x ; gp[x]=dsu(gp[x]) ; return gp[x] ; } void merge(int a,int b){ a=dsu(a),b=dsu(b) ; if (gpsz[a]%2) tt-=gpmn[a] ; if (gpsz[b]%2) tt-=gpmn[b] ; gp[b]=a ; gpsz[a]+=gpsz[b] ; gpmn[a]=min(gpmn[a],gpmn[b]) ; if (gpsz[a]%2) tt+=gpmn[a] ; } std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) { int Q = (int)E.size(); int N=W.size() ; std::vector<long long> R(Q, 0); int i,j ; vector <pair<int,int>> qs ; for (i = 0 ; i < Q ; i ++){ qs.push_back({E[i],i}) ; } sort(qs.begin(),qs.end()) ; vector <pair<int,int>> v ; for (i = 0 ; i < N ; i ++){ tt+=A[i] ; v.push_back({W[i],A[i]-B[i]}) ; } sort(v.begin(),v.end()) ; for (i = 0 ; i < N ; i ++){ gp[i]=i ; gpmn[i]=v[i].second ; gpsz[i]=1 ; } vector<pair<int,int>> vv ; for (i = 0 ; i < N-1 ; i ++){ vv.push_back({v[i+1].first-v[i].first,i}) ; } sort(vv.begin(),vv.end()) ; int nw=0 ; for (i = 0 ; i < Q ; i ++){ int x=qs[i].first ; while (nw<vv.size()&&vv[nw].first<=x){ merge(vv[nw].second,vv[nw].second+1) ; nw++ ; } R[qs[i].second]=tt ; } return R; } //////////////////////////////////////////////////////////////////////// #ifdef test //grader{ // #include "nile.h" #include <cassert> #include <cstdio> #include <vector> int main() { int N; assert(1 == scanf("%d", &N)); std::vector<int> W(N), A(N), B(N); for (int i = 0; i < N; i++) assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i])); int Q; assert(1 == scanf("%d", &Q)); std::vector<int> E(Q); for (int j = 0; j < Q; j++) assert(1 == scanf("%d", &E[j])); fclose(stdin); std::vector<long long> R = calculate_costs(W, A, B, E); int S = (int)R.size(); for (int j = 0; j < S; j++) printf("%lld\n", R[j]); fclose(stdout); return 0; } //grader} #endif
#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...