Submission #47293

#	Time	Username	Problem	Language	Result	Execution time	Memory
47293		Talant	Fireworks (APIO16_fireworks)	C++17	0 / 100	11 ms	9720 KiB

fireworks

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;

int n,m;
int x,w;
int d[N];
int dd[N],u[N];
int cur;
int mx,ans = inf;


vector <pair<int,int> > g[N];
vector <int> t[N];

void dfs (int v,int p = 0) {
      d[v] += u[v];
      d[v] += d[p];

      if (v > n)
            t[v].pb(v);

      for (auto to : g[v]) {
            dfs(to.fr,v);
            for (auto x : t[to.fr])
                  t[v].pb(x);
      }
}
int check(int v,int add) {
      int sum = 0,sum1 = 0,cn = 0,cnt = 0,c = 0;
      for (auto to : t[v]) {
            if (dd[to] < 0)
                  sum += dd[to],cnt ++;
            else if (dd[to] > 0)
                  sum1 += dd[to],cn ++;
            else
                  c ++;
      }
      if (add >= 0) {
            cnt += c;
            sum1 -= abs(cn * add);
            sum -= abs(cnt * add);
      }
      else {
            cn += c;
            sum1 += abs(cn * add);
            sum += abs(cnt * add);
      }
//      if (v == 3 && add == 1 && cur == 14)
//      cout << abs(sum) + abs(sum1) << endl;
      return (abs(sum) + abs(sum1));
}
void f (int v) {
      if (v > 1) {
            int l = -300,r = 300;
            while (r - l >= 3) {
                  int m1 = l + (r - l) / 3;
                  int m2 = r - (r - l) / 3;
                  if (check(v,m1) < check(v,m2))
                        r = m2;
                  else
                        l = m1;
            }
            int o = inf,oo = inf;
            for (int i = l; i <= r; i ++) {
                  if (o > check(v,i)) {
                        o = check(v,i);
                        oo = i;
                  }
                  else if(o == check(v,i)) {
                        if (abs(oo) > abs(i))
                              oo = i;
                  }
            }
            if (oo >= 0) {
                  for (auto to : t[v])
                        dd[to] -= abs(oo);
            }
            else {
                  for (auto to : t[v])
                        dd[to] += abs(oo);
            }
            mx += abs(oo);
      }
      for (auto to : g[v]) {
            f(to.fr);
      }
}
main () {
      cin >> n >> m;

      for (int i = 2; i <= n + m; i ++) {
            cin >> x >> w;
            g[x].pb(mk(i,w));
            u[i] = w;
      }

      dfs(1);

      for (int i = 0; i <= 300; i ++) {
            for (int j = n + 1; j <= n + m; j ++) {
                  dd[j] = i - d[j];
            }

            cur = i;
            f(1);
            ans = min(ans,mx);
            mx = 0;
      }
      cout << ans << endl;
}

Compilation message (stderr)

fireworks.cpp:100:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45