oj.uz

답안 #935196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935196 2024-02-28T19:26:03 Z velislavgarkov Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 2000 ms 69064 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAXN=2e5+3;
#define endl '\n'
//#define getchar getchar_unlocked
struct Node {
    long long mx, lazyadd, lazyset;
};
vector <int> v[MAXN];
set <int> vals;
vector <pair <int, long long> > dp[MAXN];
Node tree[4*MAXN];
long long c[MAXN];
int h[MAXN], cnt;
pair <int,int> kopie[MAXN];
int ss[MAXN];

void merge_lazy(int par, int ch) {
    if (tree[par].lazyset!=-1) {
        tree[ch].lazyset=tree[par].lazyset;
        tree[ch].lazyadd=0;
        return;
    }

    if (tree[ch].lazyset==-1) tree[ch].lazyadd+=tree[par].lazyadd;
    else tree[ch].lazyset+=tree[par].lazyadd;
}

void push_lazy(int node, int l, int r) {
    if (tree[node].lazyadd==0 && tree[node].lazyset==-1) return;

    if (tree[node].lazyadd==0) tree[node].mx=tree[node].lazyset;
    else tree[node].mx+=tree[node].lazyadd;

    if (l!=r) {
        merge_lazy(node,node*2);
        merge_lazy(node,node*2+1);
    }

    tree[node].lazyadd=0;
    tree[node].lazyset=-1;
}
void add_update(int node, int l, int r, int ql, int qr, long long ch) {
    push_lazy(node,l,r);
    if (ql>r || qr<l) return;

    if (l>=ql && r<=qr) {
        tree[node].lazyadd=ch;
        push_lazy(node,l,r);
        return;
    }

    int mid=(l+r)/2;
    add_update(node*2,l,mid,ql,qr,ch);
    add_update(node*2+1,mid+1,r,ql,qr,ch);

    tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx);
}
void set_update(int node, int l, int r, int ql, int qr, long long ch) {
    push_lazy(node,l,r);
    if (ql>r || qr<l) return;

    if (l>=ql && r<=qr) {
        tree[node].lazyset=ch;
        push_lazy(node,l,r);
        return;
    }

    int mid=(l+r)/2;
    set_update(node*2,l,mid,ql,qr,ch);
    set_update(node*2+1,mid+1,r,ql,qr,ch);

    tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx);
}
long long query(int node, int l, int r, int qind) {
    push_lazy(node,l,r);
    if (l==r) return tree[node].mx;

    int mid=(l+r)/2;
    if (qind<=mid) return query(node*2,l,mid,qind);
    return query(node*2+1,mid+1,r,qind);
}
int find_ind(int node, int l, int r, int ql, int qr, long long ch) {
    push_lazy(node,l,r);
    if (ql>r || qr<l || tree[node].mx<=ch) return -1;

    if (l==r) return l;
    int mid=(l+r)/2;
    int res=find_ind(node*2,l,mid,ql,qr,ch);
    if (res!=-1) return res;
    return find_ind(node*2+1,mid+1,r,ql,qr,ch);
}
void find_ss(int x) {
    ss[x]=1;
    for (int i=0;i<v[x].size();++i) {
        find_ss(v[x][i]);
        ss[x]+=ss[v[x][i]];
    }
    for (int i=1;i<v[x].size();++i) {
        if (ss[v[x][i]]>ss[v[x][0]]) swap(v[x][0],v[x][i]);
    }
}
void find_dp(int x) {
    if (v[x].empty()) {
        add_update(1,1,cnt,h[x]+1,cnt,c[x]);
        vals.insert(h[x]);
        vals.insert(cnt);
        return;
    }

    long long cur_res;
    int k;
    cur_res=0;
    for (int i=1;i<v[x].size();++i) {
        find_dp(v[x][i]);
        
        dp[v[x][i]].resize(vals.size());
        k=0;
        for (auto j:vals) {
            dp[v[x][i]][k]={j,query(1,1,cnt,j)};
            k++;
        }

        cur_res+=query(1,1,cnt,(*vals.lower_bound(h[x])));

        set_update(1,1,cnt,1,cnt,0);
    }

    find_dp(v[x][0]);
    cur_res+=query(1,1,cnt,(*vals.lower_bound(h[x])));

    for (int i=1;i<v[x].size();++i) {
        for (int j=0;j<dp[v[x][i]].size();j++) {
            int newv=dp[v[x][i]][j].first;
            set_update(1,1,cnt,newv,newv, query(1,1,cnt, (*vals.lower_bound(newv)) ) );
        }
    }

    for (int i=1;i<v[x].size();++i) {
        int ch=v[x][i];
        for (int j=0;j<dp[ch].size();j++) {
            if (j==0) add_update(1,1,cnt,1,dp[ch][j].first,dp[ch][j].second);
            else {
                add_update(1,1,cnt,dp[ch][j-1].first+1,dp[ch][j].first,dp[ch][j].second);
            }
            vals.insert(dp[ch][j].first);
        }
    }
    add_update(1,1,cnt,1,cnt,c[x]);

    int pos=find_ind(1,1,cnt,1,h[x],cur_res);
    if (pos!=-1) {
        set_update(1,1,cnt,pos,h[x],cur_res);
    }
    
    vals.insert(h[x]);
}
int read() {
    int res=0;
    char c=getchar();
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9') {
        res=res*10+c-'0';
        c=getchar();
    }
    return res;
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, par;
    n=read();
    for (int i=1;i<=n;++i) {
        par=read();
        h[i]=read();
        c[i]=read();
        if (i!=1) v[par].push_back(i);
        kopie[i].first=h[i];
        kopie[i].second=i;
    }
    sort(kopie+1,kopie+n+1);
    cnt=0;
    for (int i=1;i<=n;++i) {
        if (kopie[i].first!=kopie[i-1].second) cnt++;
        h[kopie[i].second]=cnt;
    }
    cnt++;
    find_ss(1);
    for (int j=1;j<=4*cnt;++j) {
        tree[j].lazyset=-1;
    }
    find_dp(1);
    cout << query(1,1,cnt,1) << endl;
    return 0;
}
/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
*/

Compilation message

worst_reporter2.cpp: In function 'void find_ss(int)':
worst_reporter2.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i=0;i<v[x].size();++i) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i=1;i<v[x].size();++i) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'void find_dp(int)':
worst_reporter2.cpp:117:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (int i=1;i<v[x].size();++i) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i=1;i<v[x].size();++i) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for (int j=0;j<dp[v[x][i]].size();j++) {
      |                      ~^~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i=1;i<v[x].size();++i) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for (int j=0;j<dp[ch].size();j++) {
      |                      ~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Execution timed out 2089 ms 69064 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Execution timed out 2089 ms 69064 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Execution timed out 2089 ms 69064 KB Time limit exceeded
6 Halted 0 ms 0 KB -