oj.uz

답안 #725855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725855 2023-04-18T07:41:26 Z MohammadAghil Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 581 ms 46548 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)size(x)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pp;

void dbg(){
     cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          // freopen("inp.txt", "r", stdin);
          // freopen("out.txt", "w", stdout);
          #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
     #else
          #define er(...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7, mod2 = 1e9 + 9, maxn = 2e5 + 5, lg = 21, inf = ll(1e9) + 5;

ll pw(ll a, ll b){
     if(b == 0) return 1;
     ll k = pw(a, b>>1);
     return k*k*(b&1ll?a:1);  
}

vector<int> adj[maxn];
ll par[maxn], H[maxn], C[maxn], nxt[maxn];
int h[maxn], cnt[maxn], top[maxn], st[maxn], en[maxn], t, eu[maxn];
ll dp[maxn];
bool vis[maxn], vis2[maxn];
vector<int> srt;
int root[maxn];

void dfs2(int r){
     srt.pb(r);
     vis2[r] = true;
     for(int c: adj[r]) if(!vis2[c]) dfs2(c);
}


int seg[maxn<<2];

int get(int l, int r, int x = 1, int lx = 0, int rx = t){
     if(l <= lx && r >= rx) return seg[x];
     int mid = (lx + rx)>>1;
     int res = -1;
     if(mid < r) res = get(l, r, x<<1|1, mid, rx);
     if(res + 1) return res;
     if(l < mid) return get(l, r, x<<1, lx, mid);
     return -1;
}

void upd(int i, bool act, int x = 1, int lx = 0, int rx = t){
     if(lx + 1 == rx){
          seg[x] = act? i: -1;
          return;
     }
     int mid = (lx + rx)>>1;
     if(i < mid) upd(i, act, x<<1, lx, mid);
     else upd(i, act, x<<1|1, mid, rx);
     seg[x] = max(seg[x<<1], seg[x<<1|1]);
}

ll fen[maxn];
ll getf(int i){
     ll res = 0;
     for(i++; i; i -= i&-i) res += fen[i];
     return res;
}
ll getf(int l, int r){
     return getf(r-1) - getf(l-1);
}
ll getu(int u){
     return getf(st[u], en[u]);
}
void updf(int i, ll k){
     for(i++; i < maxn; i += i&-i) fen[i] += k;
}

void dfs(int r, int p, int rt){
     root[r] = rt;
     par[r] = p;
     cnt[r] = 1;
     for(int c: adj[r]) if(!vis[c] && c - p){
          h[c] = h[r] + 1;
          dfs(c, r, rt);
          cnt[r] += cnt[c];
     }
}

void dfsHLD(int r, int p, int tp){
     eu[t] = r;
     top[r] = tp, st[r] = t++;
     pp bst = {-1, -1};
     for(int c: adj[r]) if(!vis[c] && c - p) bst = max(bst, {cnt[c], c});
     if(bst.ff + 1){
          dfsHLD(bst.ss, r, tp);
          for(int c: adj[r]) if(c - bst.ss && !vis[c] && c - p) dfsHLD(c, r, c);
     }
     en[r] = t;
}

void add(int u){
     dp[u] = getu(u) + C[u];
     ll sm = C[u], cr = u;
     upd(st[u], true);
     u = par[u];
     if(u + 1){
          updf(st[u], sm);
     }
     while(u + 1){
          int x = get(st[top[u]], st[u] + 1);
          if(x + 1){
               x = eu[x];
               if(par[x] + 1) updf(st[par[x]], -sm);
               ll t = getu(x);
               if(t > dp[x]){
                    sm = t - dp[x];
                    upd(st[x], false);
                    u = par[x];
                    if(u + 1) updf(st[u], sm);
               } else break;
          } else u = par[top[u]];
     }
}

int main(){ IOS();  
     int n; cin >> n;
     ll sum = 0;
     rep(i,0,n){
          cin >> nxt[i] >> H[i] >> C[i];
          nxt[i]--;
          sum += C[i];
          adj[i].pb(nxt[i]), adj[nxt[i]].pb(i);
     }
     fill(seg, seg + (maxn<<2), -1);
     rep(i,0,n){
          if(!vis2[i]){
               dfs2(i);
               int a = i, b = i;
               do{
                    a = nxt[a], b = nxt[nxt[b]];
               } while(a - b);
               map<int, vector<int>> is;
               do{
                    vis[a] = true;
                    a = nxt[a];
               } while(a - b);
               do{
                    dfs(a, -1, a);
                    dfsHLD(a, -1, a);
                    is[H[a]].pb(a);
                    a = nxt[a];
               } while(a - b);
               ll sm = 0;
               ll res = 0;
               sort(all(srt), [&](int i, int j){
                    return pp(H[i], h[i]) > pp(H[j], h[j]);
               });
               rep(i,0,sz(srt)){
                    int u = srt[i];
                    sm -= getu(root[u]);
                    add(u);
                    sm += getu(root[u]);
                    if(i == sz(srt)-1 || H[u] - H[srt[i+1]]){
                         if(is.count(H[u])){
                              ll t = sm;
                              for(int c: is[H[u]]){
                                   t += C[c];
                              }
                              res = max(res, t);
                         }
                    }
               }
               sum -= max(res, sm);
               srt.clear();
          }
     }
     cout << sum << '\n';
     return 0;
}

Compilation message

worst_reporter2.cpp: In function 'void add(int)':
worst_reporter2.cpp:120:20: warning: unused variable 'cr' [-Wunused-variable]
  120 |      ll sm = C[u], cr = u;
      |                    ^~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 5 ms 8276 KB Output is correct
3 Correct 4 ms 8276 KB Output is correct
4 Correct 5 ms 8244 KB Output is correct
5 Correct 9 ms 8984 KB Output is correct
6 Correct 10 ms 8896 KB Output is correct
7 Correct 9 ms 8916 KB Output is correct
8 Correct 10 ms 8916 KB Output is correct
9 Correct 10 ms 8916 KB Output is correct
10 Correct 11 ms 8916 KB Output is correct
11 Correct 8 ms 8892 KB Output is correct
12 Correct 10 ms 9300 KB Output is correct
13 Correct 10 ms 9368 KB Output is correct
14 Correct 10 ms 9172 KB Output is correct
15 Correct 10 ms 9044 KB Output is correct
16 Correct 10 ms 8892 KB Output is correct
17 Correct 10 ms 8916 KB Output is correct
18 Correct 9 ms 8916 KB Output is correct
19 Correct 9 ms 9152 KB Output is correct
20 Correct 9 ms 9044 KB Output is correct
21 Correct 9 ms 9044 KB Output is correct
22 Correct 8 ms 8892 KB Output is correct
23 Correct 7 ms 8916 KB Output is correct
24 Correct 10 ms 9172 KB Output is correct
25 Correct 9 ms 9160 KB Output is correct
26 Correct 8 ms 9300 KB Output is correct
27 Correct 9 ms 9080 KB Output is correct
28 Correct 11 ms 9148 KB Output is correct
29 Correct 9 ms 9148 KB Output is correct
30 Correct 9 ms 9152 KB Output is correct
31 Correct 10 ms 9148 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 5 ms 8276 KB Output is correct
3 Correct 4 ms 8276 KB Output is correct
4 Correct 5 ms 8244 KB Output is correct
5 Correct 9 ms 8984 KB Output is correct
6 Correct 10 ms 8896 KB Output is correct
7 Correct 9 ms 8916 KB Output is correct
8 Correct 10 ms 8916 KB Output is correct
9 Correct 10 ms 8916 KB Output is correct
10 Correct 11 ms 8916 KB Output is correct
11 Correct 8 ms 8892 KB Output is correct
12 Correct 10 ms 9300 KB Output is correct
13 Correct 10 ms 9368 KB Output is correct
14 Correct 10 ms 9172 KB Output is correct
15 Correct 10 ms 9044 KB Output is correct
16 Correct 10 ms 8892 KB Output is correct
17 Correct 10 ms 8916 KB Output is correct
18 Correct 9 ms 8916 KB Output is correct
19 Correct 9 ms 9152 KB Output is correct
20 Correct 9 ms 9044 KB Output is correct
21 Correct 9 ms 9044 KB Output is correct
22 Correct 8 ms 8892 KB Output is correct
23 Correct 7 ms 8916 KB Output is correct
24 Correct 10 ms 9172 KB Output is correct
25 Correct 9 ms 9160 KB Output is correct
26 Correct 8 ms 9300 KB Output is correct
27 Correct 9 ms 9080 KB Output is correct
28 Correct 11 ms 9148 KB Output is correct
29 Correct 9 ms 9148 KB Output is correct
30 Correct 9 ms 9152 KB Output is correct
31 Correct 10 ms 9148 KB Output is correct
32 Correct 11 ms 8956 KB Output is correct
33 Correct 458 ms 31032 KB Output is correct
34 Correct 483 ms 31080 KB Output is correct
35 Correct 525 ms 31036 KB Output is correct
36 Correct 482 ms 31132 KB Output is correct
37 Correct 424 ms 31048 KB Output is correct
38 Correct 363 ms 31132 KB Output is correct
39 Correct 430 ms 46448 KB Output is correct
40 Correct 360 ms 46484 KB Output is correct
41 Correct 218 ms 46548 KB Output is correct
42 Correct 369 ms 38668 KB Output is correct
43 Correct 335 ms 38708 KB Output is correct
44 Correct 422 ms 30824 KB Output is correct
45 Correct 433 ms 30856 KB Output is correct
46 Correct 266 ms 30932 KB Output is correct
47 Correct 297 ms 37848 KB Output is correct
48 Correct 305 ms 37916 KB Output is correct
49 Correct 212 ms 37904 KB Output is correct
50 Correct 194 ms 30164 KB Output is correct
51 Correct 183 ms 30144 KB Output is correct
52 Correct 279 ms 38352 KB Output is correct
53 Correct 271 ms 38312 KB Output is correct
54 Correct 161 ms 46520 KB Output is correct
55 Correct 278 ms 38228 KB Output is correct
56 Correct 255 ms 42304 KB Output is correct
57 Correct 250 ms 43936 KB Output is correct
58 Correct 249 ms 38672 KB Output is correct
59 Correct 234 ms 38624 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 5 ms 8276 KB Output is correct
3 Correct 4 ms 8276 KB Output is correct
4 Correct 5 ms 8244 KB Output is correct
5 Correct 9 ms 8984 KB Output is correct
6 Correct 10 ms 8896 KB Output is correct
7 Correct 9 ms 8916 KB Output is correct
8 Correct 10 ms 8916 KB Output is correct
9 Correct 10 ms 8916 KB Output is correct
10 Correct 11 ms 8916 KB Output is correct
11 Correct 8 ms 8892 KB Output is correct
12 Correct 10 ms 9300 KB Output is correct
13 Correct 10 ms 9368 KB Output is correct
14 Correct 10 ms 9172 KB Output is correct
15 Correct 10 ms 9044 KB Output is correct
16 Correct 10 ms 8892 KB Output is correct
17 Correct 10 ms 8916 KB Output is correct
18 Correct 9 ms 8916 KB Output is correct
19 Correct 9 ms 9152 KB Output is correct
20 Correct 9 ms 9044 KB Output is correct
21 Correct 9 ms 9044 KB Output is correct
22 Correct 8 ms 8892 KB Output is correct
23 Correct 7 ms 8916 KB Output is correct
24 Correct 10 ms 9172 KB Output is correct
25 Correct 9 ms 9160 KB Output is correct
26 Correct 8 ms 9300 KB Output is correct
27 Correct 9 ms 9080 KB Output is correct
28 Correct 11 ms 9148 KB Output is correct
29 Correct 9 ms 9148 KB Output is correct
30 Correct 9 ms 9152 KB Output is correct
31 Correct 10 ms 9148 KB Output is correct
32 Correct 11 ms 8956 KB Output is correct
33 Correct 458 ms 31032 KB Output is correct
34 Correct 483 ms 31080 KB Output is correct
35 Correct 525 ms 31036 KB Output is correct
36 Correct 482 ms 31132 KB Output is correct
37 Correct 424 ms 31048 KB Output is correct
38 Correct 363 ms 31132 KB Output is correct
39 Correct 430 ms 46448 KB Output is correct
40 Correct 360 ms 46484 KB Output is correct
41 Correct 218 ms 46548 KB Output is correct
42 Correct 369 ms 38668 KB Output is correct
43 Correct 335 ms 38708 KB Output is correct
44 Correct 422 ms 30824 KB Output is correct
45 Correct 433 ms 30856 KB Output is correct
46 Correct 266 ms 30932 KB Output is correct
47 Correct 297 ms 37848 KB Output is correct
48 Correct 305 ms 37916 KB Output is correct
49 Correct 212 ms 37904 KB Output is correct
50 Correct 194 ms 30164 KB Output is correct
51 Correct 183 ms 30144 KB Output is correct
52 Correct 279 ms 38352 KB Output is correct
53 Correct 271 ms 38312 KB Output is correct
54 Correct 161 ms 46520 KB Output is correct
55 Correct 278 ms 38228 KB Output is correct
56 Correct 255 ms 42304 KB Output is correct
57 Correct 250 ms 43936 KB Output is correct
58 Correct 249 ms 38672 KB Output is correct
59 Correct 234 ms 38624 KB Output is correct
60 Correct 4 ms 8148 KB Output is correct
61 Correct 6 ms 8276 KB Output is correct
62 Correct 4 ms 8276 KB Output is correct
63 Correct 4 ms 8276 KB Output is correct
64 Incorrect 581 ms 32984 KB Output isn't correct
65 Halted 0 ms 0 KB -