oj.uz

Submission #667360

# Submission time Handle Problem Language Result Execution time Memory
667360 2022-12-01T07:42:21 Z MohammadAghil Fireworks (APIO16_fireworks) C++17
7 / 100
 5 ms 7380 KB 
      #include <bits/stdc++.h>
  #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<ll, ll> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     //      freopen("inp.txt", "r", stdin);
     //      freopen("out.txt", "w", stdout);
     // #else
     //      #define er(args ...) 0
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 9, maxn = 3e5 + 5, lg = 17, inf = ll(1e18) + 5, p = 9973;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}
 
vector<pp> adj[maxn];
ll ans;

pp dfs(int r){
     if(sz(adj[r]) == 0) return {0, 0};
     vector<pp> a;
     for(auto[c, w]: adj[r]){
          pp res = dfs(c);
          a.pb({res.ff + w, res.ss + w});
     }
     pp res;
     ll lx = -inf, rx = inf;
     while(lx + 1 < rx){
          ll mid = (lx + rx)>>1ll;
          int cnt = 0;
          for(auto[l, r]: a){
               if(r < mid) cnt--;
               if(l >= mid) cnt++;
          }
          if(cnt >= 0) lx = mid;
          else rx = mid;
     }
     res.ss = lx;

     lx = -inf, rx = inf;
     while(lx + 1 < rx){
          ll mid = (lx + rx)>>1ll;
          int cnt = 0;
          for(auto[l, r]: a){
               if(r <= mid) cnt++;
               if(l > mid) cnt--;
          }
          if(cnt >= 0) rx = mid;
          else lx = mid;
     }
     res.ff = rx;

     assert(res.ff <= res.ss);

     for(auto[l, r]: a){
          if(rx < l || rx > r) ans += min(abs(rx - l), abs(rx - r)); 
     }

     // er(r, res.ff, res.ss);
     return res;
}

int main(){ IOS();
     int n, m; cin >> n >> m;
     rep(i,1,n+m){
          int p, w; cin >> p >> w; p--;
          adj[p].pb({i, w});
     }
     dfs(0);
     cout << ans << '\n';
     return 0-0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7364 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7344 KB Output is correct
3 Incorrect 4 ms 7252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7364 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7252 KB Output is correct
12 Correct 4 ms 7344 KB Output is correct
13 Incorrect 4 ms 7252 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7364 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7252 KB Output is correct
12 Correct 4 ms 7344 KB Output is correct
13 Incorrect 4 ms 7252 KB Output isn't correct
14 Halted 0 ms 0 KB -