Submission #932513

#	Time	Username	Problem	Language	Result	Execution time	Memory
932513		andrei_boaca	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	459 ms	109600 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e17;
map<ll,ll> nrm;
ll nr;
vector<ll> muchii[400005];
vector<ll> edges[400005];
ll to[400005];
ll n,par[400005],v[400005],cost[400005];
set<pll> setik[400005];
ll ans,retard;
ll aib[400005];
ll lsb(ll x)
{
    return x&(-x);
}
void update(ll poz,ll val)
{
    for(ll i=poz;i<=nr+1;i+=lsb(i))
        aib[i]+=val;
}
ll suma(ll poz)
{
    ll rez=0;
    for(ll i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
bool use[400005];
void add(ll nod,ll poz,ll val)
{
    auto it=setik[nod].lower_bound({poz,0});
    if((*it).first==poz)
    {
        ll x=(*it).second+val;
        setik[nod].erase(it);
        setik[nod].insert({poz,x});
    }
    else
        setik[nod].insert({poz,val});
}
void dfs(ll nod)
{
    use[nod]=1;
    if(muchii[nod].empty())
    {
        add(nod,v[nod]+1,cost[nod]);
        return;
    }
    ll maxim=0;
    ll who=0;
    for(int i:muchii[nod])
    {
        dfs(i);
        if(setik[i].size()>maxim)
        {
            maxim=setik[i].size();
            who=i;
        }
    }
    swap(setik[nod],setik[who]);
    for(int i:muchii[nod])
        if(i!=who)
        {
            for(auto j:setik[i])
                add(nod,j.first,j.second);
            setik[i].clear();
        }
    add(nod,1,cost[nod]);
    ll dif=cost[nod];
    while(!setik[nod].empty()&&dif>0)
    {
        auto it=prev(setik[nod].upper_bound({v[nod],INF}));
        ll poz=(*it).first;
        ll x=(*it).second;
        ll val=min(dif,x);
        x-=val;
        dif-=val;
        setik[nod].erase(it);
        if(x!=0)
            setik[nod].insert({poz,x});
    }
    add(nod,v[nod]+1,cost[nod]);
}
void initdfs(int nod,int cod)
{
    use[nod]=1;
    for(int i:edges[nod])
        if(!use[i])
        {
            muchii[cod].push_back(i);
            initdfs(i,i);
        }
}
bool byv(int a,int b)
{
    return v[a]<v[b];
}
void solve(ll start)
{
    retard++;
    vector<ll> nodes;
    while(!use[start])
    {
        use[start]=1;
        nodes.push_back(start);
        start=to[start];
    }
    vector<int> ciclu;
    ciclu.push_back(start);
    while(!nodes.empty())
    {
        if(nodes.back()==start)
            break;
        ciclu.push_back(nodes.back());
        nodes.pop_back();
    }
    for(int i:nodes)
        use[i]=0;
    for(int i:ciclu)
        initdfs(i,retard);
    dfs(retard);
    for(auto i:setik[retard])
        update(i.first,i.second);
    ll s=0;
    sort(ciclu.begin(),ciclu.end(),byv);
    for(int i:ciclu)
        s+=cost[i];
    ll minim=suma(1)+s;
    for(int i=0;i<ciclu.size();i++)
    {
        ll improve=0;
        int j=i;
        ll ind=v[ciclu[i]];
        while(j<ciclu.size()&&v[ciclu[j]]==ind)
        {
            improve+=cost[ciclu[j]];
            j++;
        }
        j--;
        i=j;
        ll val=suma(ind)+s-improve;
        minim=min(minim,val);
    }
    for(auto i:setik[retard])
        update(i.first,-i.second);
    ans+=minim;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    vector<ll> vals;
    for(int i=1;i<=n;i++)
    {
        cin>>to[i]>>v[i]>>cost[i];
        vals.push_back(v[i]);
        edges[i].push_back(to[i]);
        edges[to[i]].push_back(i);
    }
    sort(vals.begin(),vals.end());
    vals.erase(unique(vals.begin(),vals.end()),vals.end());
    for(int i=0;i<vals.size();i++)
        nrm[vals[i]]=i+1;
    nr=vals.size();
    for(int i=1;i<=n;i++)
        v[i]=nrm[v[i]];
    retard=n;
    for(int i=1;i<=n;i++)
        if(!use[i])
            solve(i);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void dfs(ll)':
worst_reporter2.cpp:58:27: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   58 |         if(setik[i].size()>maxim)
      |            ~~~~~~~~~~~~~~~^~~~~~
worst_reporter2.cpp: In function 'void solve(ll)':
worst_reporter2.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int i=0;i<ciclu.size();i++)
      |                 ~^~~~~~~~~~~~~
worst_reporter2.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         while(j<ciclu.size()&&v[ciclu[j]]==ind)
      |               ~^~~~~~~~~~~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 21 / 21