Submission #667360

#	Time	Username	Problem	Language	Result	Execution time	Memory
667360		MohammadAghil	Fireworks (APIO16_fireworks)	C++17	7 / 100	5 ms	7380 KiB

fireworks

      #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 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45