oj.uz

답안 #725840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725840 2023-04-18T07:22:08 Z MohammadAghil Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 588 ms 49496 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 -= getu(c) - dp[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 5 ms 8276 KB Output is correct
2 Correct 6 ms 8276 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 4 ms 8240 KB Output is correct
5 Correct 10 ms 8892 KB Output is correct
6 Correct 12 ms 8916 KB Output is correct
7 Correct 10 ms 8888 KB Output is correct
8 Correct 12 ms 8880 KB Output is correct
9 Correct 10 ms 8916 KB Output is correct
10 Correct 13 ms 8968 KB Output is correct
11 Correct 9 ms 8896 KB Output is correct
12 Correct 11 ms 9256 KB Output is correct
13 Correct 14 ms 9296 KB Output is correct
14 Correct 11 ms 9152 KB Output is correct
15 Correct 11 ms 9172 KB Output is correct
16 Correct 11 ms 8916 KB Output is correct
17 Correct 13 ms 8916 KB Output is correct
18 Correct 12 ms 8872 KB Output is correct
19 Correct 10 ms 9132 KB Output is correct
20 Correct 9 ms 9152 KB Output is correct
21 Correct 9 ms 9036 KB Output is correct
22 Correct 9 ms 8916 KB Output is correct
23 Correct 10 ms 8888 KB Output is correct
24 Correct 11 ms 9172 KB Output is correct
25 Correct 11 ms 9116 KB Output is correct
26 Correct 9 ms 9272 KB Output is correct
27 Correct 8 ms 9100 KB Output is correct
28 Correct 9 ms 9172 KB Output is correct
29 Correct 12 ms 9156 KB Output is correct
30 Correct 10 ms 9120 KB Output is correct
31 Correct 9 ms 9044 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 6 ms 8276 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 4 ms 8240 KB Output is correct
5 Correct 10 ms 8892 KB Output is correct
6 Correct 12 ms 8916 KB Output is correct
7 Correct 10 ms 8888 KB Output is correct
8 Correct 12 ms 8880 KB Output is correct
9 Correct 10 ms 8916 KB Output is correct
10 Correct 13 ms 8968 KB Output is correct
11 Correct 9 ms 8896 KB Output is correct
12 Correct 11 ms 9256 KB Output is correct
13 Correct 14 ms 9296 KB Output is correct
14 Correct 11 ms 9152 KB Output is correct
15 Correct 11 ms 9172 KB Output is correct
16 Correct 11 ms 8916 KB Output is correct
17 Correct 13 ms 8916 KB Output is correct
18 Correct 12 ms 8872 KB Output is correct
19 Correct 10 ms 9132 KB Output is correct
20 Correct 9 ms 9152 KB Output is correct
21 Correct 9 ms 9036 KB Output is correct
22 Correct 9 ms 8916 KB Output is correct
23 Correct 10 ms 8888 KB Output is correct
24 Correct 11 ms 9172 KB Output is correct
25 Correct 11 ms 9116 KB Output is correct
26 Correct 9 ms 9272 KB Output is correct
27 Correct 8 ms 9100 KB Output is correct
28 Correct 9 ms 9172 KB Output is correct
29 Correct 12 ms 9156 KB Output is correct
30 Correct 10 ms 9120 KB Output is correct
31 Correct 9 ms 9044 KB Output is correct
32 Correct 10 ms 8916 KB Output is correct
33 Correct 553 ms 34036 KB Output is correct
34 Correct 495 ms 34148 KB Output is correct
35 Correct 557 ms 34028 KB Output is correct
36 Correct 465 ms 34080 KB Output is correct
37 Correct 484 ms 34064 KB Output is correct
38 Correct 450 ms 34068 KB Output is correct
39 Correct 456 ms 49436 KB Output is correct
40 Correct 390 ms 49476 KB Output is correct
41 Correct 234 ms 49476 KB Output is correct
42 Correct 428 ms 41552 KB Output is correct
43 Correct 410 ms 41624 KB Output is correct
44 Correct 557 ms 33788 KB Output is correct
45 Correct 470 ms 33848 KB Output is correct
46 Correct 288 ms 33756 KB Output is correct
47 Correct 308 ms 40872 KB Output is correct
48 Correct 342 ms 40852 KB Output is correct
49 Correct 230 ms 40884 KB Output is correct
50 Correct 256 ms 32996 KB Output is correct
51 Correct 188 ms 33120 KB Output is correct
52 Correct 300 ms 41288 KB Output is correct
53 Correct 268 ms 41348 KB Output is correct
54 Correct 183 ms 49496 KB Output is correct
55 Correct 301 ms 41080 KB Output is correct
56 Correct 279 ms 45168 KB Output is correct
57 Correct 257 ms 46948 KB Output is correct
58 Correct 257 ms 41660 KB Output is correct
59 Correct 264 ms 41664 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 6 ms 8276 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 4 ms 8240 KB Output is correct
5 Correct 10 ms 8892 KB Output is correct
6 Correct 12 ms 8916 KB Output is correct
7 Correct 10 ms 8888 KB Output is correct
8 Correct 12 ms 8880 KB Output is correct
9 Correct 10 ms 8916 KB Output is correct
10 Correct 13 ms 8968 KB Output is correct
11 Correct 9 ms 8896 KB Output is correct
12 Correct 11 ms 9256 KB Output is correct
13 Correct 14 ms 9296 KB Output is correct
14 Correct 11 ms 9152 KB Output is correct
15 Correct 11 ms 9172 KB Output is correct
16 Correct 11 ms 8916 KB Output is correct
17 Correct 13 ms 8916 KB Output is correct
18 Correct 12 ms 8872 KB Output is correct
19 Correct 10 ms 9132 KB Output is correct
20 Correct 9 ms 9152 KB Output is correct
21 Correct 9 ms 9036 KB Output is correct
22 Correct 9 ms 8916 KB Output is correct
23 Correct 10 ms 8888 KB Output is correct
24 Correct 11 ms 9172 KB Output is correct
25 Correct 11 ms 9116 KB Output is correct
26 Correct 9 ms 9272 KB Output is correct
27 Correct 8 ms 9100 KB Output is correct
28 Correct 9 ms 9172 KB Output is correct
29 Correct 12 ms 9156 KB Output is correct
30 Correct 10 ms 9120 KB Output is correct
31 Correct 9 ms 9044 KB Output is correct
32 Correct 10 ms 8916 KB Output is correct
33 Correct 553 ms 34036 KB Output is correct
34 Correct 495 ms 34148 KB Output is correct
35 Correct 557 ms 34028 KB Output is correct
36 Correct 465 ms 34080 KB Output is correct
37 Correct 484 ms 34064 KB Output is correct
38 Correct 450 ms 34068 KB Output is correct
39 Correct 456 ms 49436 KB Output is correct
40 Correct 390 ms 49476 KB Output is correct
41 Correct 234 ms 49476 KB Output is correct
42 Correct 428 ms 41552 KB Output is correct
43 Correct 410 ms 41624 KB Output is correct
44 Correct 557 ms 33788 KB Output is correct
45 Correct 470 ms 33848 KB Output is correct
46 Correct 288 ms 33756 KB Output is correct
47 Correct 308 ms 40872 KB Output is correct
48 Correct 342 ms 40852 KB Output is correct
49 Correct 230 ms 40884 KB Output is correct
50 Correct 256 ms 32996 KB Output is correct
51 Correct 188 ms 33120 KB Output is correct
52 Correct 300 ms 41288 KB Output is correct
53 Correct 268 ms 41348 KB Output is correct
54 Correct 183 ms 49496 KB Output is correct
55 Correct 301 ms 41080 KB Output is correct
56 Correct 279 ms 45168 KB Output is correct
57 Correct 257 ms 46948 KB Output is correct
58 Correct 257 ms 41660 KB Output is correct
59 Correct 264 ms 41664 KB Output is correct
60 Correct 5 ms 8244 KB Output is correct
61 Correct 4 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 588 ms 35836 KB Output isn't correct
65 Halted 0 ms 0 KB -