Submission #1010331

#TimeUsernameProblemLanguageResultExecution timeMemory
1010331AdamGSWorst Reporter 4 (JOI21_worst_reporter4)C++17
100 / 100
217 ms58688 KiB
#include<bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e5+7; vector<int>V[LIM]; ll A[LIM], T[LIM], C[LIM], odw[LIM], cykl[LIM], root[LIM], ile[LIM]; void DFS(int x) { ile[x]=1; for(auto i : V[x]) { DFS(i); ile[x]+=ile[i]; } rep(i, V[x].size()) if(ile[V[x][i]]>ile[V[x][0]]) swap(V[x][i], V[x][0]); } void DFS2(int x, multiset<pair<ll,ll>>&S) { if(V[x].size()) DFS2(V[x][0], S); for(int i=1; i<V[x].size(); ++i) { multiset<pair<ll,ll>>P; DFS2(V[x][i], P); for(auto j : P) S.insert(j); } ll a=C[x]; while(a) { auto it=S.lower_bound({T[x], -1}); if(it==S.begin()) break; --it; auto p=*it; S.erase(S.find(p)); if(p.nd<=a) { a-=p.nd; continue; } p.nd-=a; a=0; S.insert(p); } S.insert({T[x], C[x]}); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; rep(i, n) { cin >> A[i] >> T[i] >> C[i]; --A[i]; } rep(i, n) if(!odw[i]) { int p=i; while(!odw[p]) { odw[p]=i+1; p=A[p]; } if(odw[p]!=i+1) continue; int x=A[p]; vector<pair<ll,ll>>P; while(x!=p) { P.pb({T[x], C[x]}); cykl[x]=1; root[x]=p; x=A[x]; } P.pb({T[x], C[x]}); cykl[x]=1; root[x]=p; sort(all(P)); x=p; for(auto j : P) { T[x]=j.st; C[x]=j.nd; if(A[x]==p) A[x]=x; x=A[x]; } } rep(i, n) if(!cykl[i] && cykl[A[i]]) A[i]=root[A[i]]; rep(i, n) if(A[i]!=i) V[A[i]].pb(i); ll sum=0; rep(i, n) sum+=C[i]; rep(i, n) if(A[i]==i) { DFS(i); multiset<pair<ll,ll>>S; DFS2(i, S); for(auto j : S) sum-=j.nd; } cout << sum << '\n'; }

Compilation message (stderr)

worst_reporter2.cpp: In function 'void DFS(int)':
worst_reporter2.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
worst_reporter2.cpp:19:3: note: in expansion of macro 'rep'
   19 |   rep(i, V[x].size()) if(ile[V[x][i]]>ile[V[x][0]]) swap(V[x][i], V[x][0]);
      |   ^~~
worst_reporter2.cpp: In function 'void DFS2(int, std::multiset<std::pair<long long int, long long int> >&)':
worst_reporter2.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i=1; i<V[x].size(); ++i) {
      |                ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...