Submission #691860

#TimeUsernameProblemLanguageResultExecution timeMemory
691860AntekbWorst Reporter 4 (JOI21_worst_reporter4)C++14
100 / 100
1203 ms206432 KiB
#include<bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("trapv") #define st first #define nd second #define pb push_back #define eb emplace_back #define pp(x) pop_back(x) #define mp(a, b) make_pair(a, b) #define all(x) (x).begin(), (x).end() #define rev(x) reverse(all(x)) #define sor(x) sort(all(x)) #define sz(x) (int)(x).size() #define rsz(x) resize(x) using namespace std; ///~~~~~~~~~~~~~~~~~~~~~~~~~~ template <typename H, typename T> ostream& operator<<(ostream& os, pair<H, T> m){ return os <<"("<< m.st<<", "<<m.nd<<")"; } template <typename H> ostream& operator<<(ostream& os, vector<H> V){ os<<"{"; for(int i=0; i<V.size(); i++){ if(i)os<<" "; os<<V[i]; } os<<"}"; return os; } void debug(){cerr<<"\n";} template <typename H, typename... T> void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);} #define deb(x...) cerr<<#x<<" = ";debug(x); //#define deb(x...) ; ///~~~~~~~~~~~~~~~~~~~~~~~~~ typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii > vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef string str; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); //mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N=1<<19, INF=1e9+5, mod=1e9+7, mod2=998244353; struct modint{ int n=0; modint(){} modint(ll x){ n=x%mod; if(n<0)n+=mod; } operator int(){ return n; } modint operator+(modint a){a.n = n+a.n; if(a.n>=mod)a.n-=mod;return a;} modint operator+=(modint a){return (*this)=(*this)+a;} modint operator-(modint a){a.n = n-a.n; if(a.n<0)a.n+=mod;return a;} modint operator-=(modint a){return (*this)=(*this)-a;} modint operator*(modint a){a.n = (n*1ll*a.n)%mod; return a;} modint operator*=(modint a){return (*this)=(*this)*a;} modint operator^(const ll &m)const{ modint a(1); if(m==0)return a; if(m==1)return (*this); a=(*this)^(m/2); a*=a; return a*((*this)^(m&1)); } modint odw(){ return (*this)^((ll)mod-2); } modint operator/(modint a){return (*this)*a.odw();} modint operator/=(modint a){return (*this)=(*this)/a;} bool operator==(modint a){return a.n==n;} friend ostream& operator<<(ostream& os, modint m) { return os << m.n; } }; modint fact[N], fact2[N]; typedef vector<modint> vm; void factinit(){ fact[0]=1; for(int i=1; i<N; i++){ fact[i]=(fact[i-1]*modint(i))%mod; } fact2[N-1]=fact[N-1].odw(); for(int i=N-2; i>=0; i--){ fact2[i]=(fact2[i+1]*modint(i+1))%mod; } } modint npok(int _n, int _k){ return fact[_n]*fact2[_k]*fact2[_n-_k]; } int deg[N], A[N], H[N], C[N], czy[N]; vi E[N]; struct node{ node *l=nullptr,*r=nullptr; ll val=0, lazy=0; node(){}; void prop(){ //deb(val, lazy, l, r); if(l){ assert(l); l->val=max(l->val+lazy, val); l->lazy+=lazy; } if(r){ r->val=max(r->val+lazy, val); r->lazy+=lazy; } lazy=0; } }; node* merge(node*u, node*v){ if(!u)return v; if(!v)return u; if(!u->l){ v->val+=u->val; v->lazy+=u->val; delete u; return v; } if(!v->l){ u->val+=v->val; u->lazy+=v->val; delete v; return u; } u->prop(); v->prop(); u->l=merge(u->l, v->l); u->r=merge(u->r, v->r); delete v; return u; } void add(node* v, int L, int R, int l, int r, ll c){ if(l==L && r==R){ v->val=max(c, v->val); return; } if(!v->l){ v->l=(new node); v->r=(new node); } v->prop(); int M=(L+R)>>1; if(l<=M)add(v->l, L, M, l, min(M,r), c); if(r>M)add(v->r, M+1, R, max(l, M+1), r, c); return; } ll get_val(node* v, int L, int R, int t){ if(!v->l)return v->val; v->prop(); int M=(L+R)>>1; if(t<=M)return max(v->val, get_val(v->l, L, M, t)); else return max(v->val, get_val(v->r, M+1, R, t)); } node* dfs(int v){ //deb(v); node* root=0; for(int u:E[v]){ node *w=dfs(u); assert(w); //sum+=get_val(w, 0, N-1, H[v]); root=merge(root, w); } if(!root)root=new node; ll sum=C[v]+get_val(root, 0, N-1, H[v]); add(root, 0, N-1, 0, H[v], sum); return root; } int main(){ //factinit(); //BOOST; int n; cin>>n; vector<int> ska; ll sum=0; for(int i=1; i<=n; i++){ cin>>A[i]>>H[i]>>C[i]; deg[A[i]]++; ska.pb(H[i]); sum+=C[i]; } sor(ska); ska.resize(unique(all(ska))- ska.begin()); for(int i=1; i<=n; i++){ H[i]=lower_bound(all(ska), H[i])-ska.begin(); } vi V; for(int i=1; i<=n; i++){ if(deg[i]==0){ V.pb(i); } } for(int i=0; i<V.size(); i++){ int v=V[i]; if(!--deg[A[v]]){ V.pb(A[v]); } E[A[v]].pb(v); } vector<vi> cykle, co; vector<map<int, ll> > M; for(int i=1; i<=n; i++){ if(deg[i]){ cykle.pb({}); co.pb({}); M.resize(M.size()+1); for(int j=A[i]; deg[j]; j=A[j]){ deg[j]=0; M[M.size()-1][H[j]]+=C[j]; cykle.back().pb(j); for(int u:E[j]){ co.back().pb(u); } } } } deb(cykle); //deb(V); ll ans=0; for(int i=0; i<cykle.size(); i++){ node* root=0; for(int j:co[i]){ root=merge(root, dfs(j)); } ll part=0; for(auto j:M[i]){ if(root)part=max(part, get_val(root, 0, N-1, j.st)+j.nd); else part=max(part, j.nd); } if(root)part=max(part, get_val(root, 0, N-1, 0)); ans+=part; } cout<<sum-ans; }

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:220:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
worst_reporter2.cpp:247:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |  for(int i=0; i<cykle.size(); i++){
      |               ~^~~~~~~~~~~~~
worst_reporter2.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>) [with H = std::vector<int>; std::ostream = std::basic_ostream<char>]':
worst_reporter2.cpp:39:30:   required from 'void debug(H, T ...) [with H = std::vector<std::vector<int> >; T = {}]'
worst_reporter2.cpp:244:2:   required from here
worst_reporter2.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
worst_reporter2.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>) [with H = int; std::ostream = std::basic_ostream<char>]':
worst_reporter2.cpp:31:5:   required from 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>) [with H = std::vector<int>; std::ostream = std::basic_ostream<char>]'
worst_reporter2.cpp:39:30:   required from 'void debug(H, T ...) [with H = std::vector<std::vector<int> >; T = {}]'
worst_reporter2.cpp:244:2:   required from here
worst_reporter2.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...