Submission #1053103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053103		vjudge1	Jobs (BOI24_jobs)	C++17	40 / 100	172 ms	31312 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e18;
const int N = 3e5+10, K = 20;
int n, p[N], h[N], par[N][K];
ll s, x[N];
vector<int> child[N];


ll dfs(int v)
{
  for(int c : child[v])
    x[v] += dfs(c);
  return max(x[v], 0ll);
}

void subtask1()
{
  cout << dfs(0) << endl;
  exit(0);
}

void subtask23()
{
  set<pair<ll, int> > st;
  for(int i = 1; i <= n; i ++)
    if(p[i] == 0) st.insert({x[i], i});

  ll init = s;
  while(st.size())
    {
      int v = st.rbegin()->second;
      st.erase(--st.end());
      if(s + x[v] >= 0)
	{
	  if(child[v].empty())
	    s += max(0ll, x[v]);
	  else
	    {
	      int c = child[v][0];
	      if(x[v] >= 0) s += x[v];
	      else x[c] += x[v];
	      st.insert({x[c], c});
	    }
	}
    }
  cout << s - init << endl;
  exit(0);
}

void dfs_lca(int v)
{
  for(int i = 1; i < K; i ++) par[v][i] = par[par[v][i - 1]][i - 1];

  for(int c : child[v])
    {
      par[c][0] = v;
      h[c] = h[v] + 1;
      dfs_lca(c);
    }
}

int lca(int a, int b)
{
  if(h[a] < h[b]) swap(a, b);
  for(int i = K - 1; i >= 0; i--)
    if(h[par[a][i]] >= h[b]) a = par[a][i];

  if(a == b) return a;
  for(int i = K - 1; i >= 0; i--)
    if(par[a][i] != par[b][i])
      a = par[a][i], b = par[b][i];
  return par[a][0];
}

int main()
{
  cin >> n >> s;

  bool s23 = true;
  for(int i = 1; i <= n; i ++)
    {
      cin >> x[i] >> p[i];
      s23 &= (p[i] == 0 || p[i] == i - 1);
      child[p[i]].push_back(i);
    }

  if(s == inf) subtask1();
  if(s23) subtask23();

  dfs_lca(0);
  
  vector<int> vec, vec2;
  for(int i = 1; i <= n; i ++)
    if(p[i] == 0)
      vec.push_back(i);
  ll init = s;
  while(vec.size())
    {
      int mx = 0;
     
      for(int i = 0; i < vec.size(); i++)
	if(x[vec[i]] > x[vec[mx]]) mx = i;
      
      swap(vec.back(), vec[mx]);
      mx = vec.back();
      vec.pop_back();
      // cerr << mx << ' ' << x[mx] << ' ' << sub[mx] << endl;
      if(s + x[mx] >= 0)
	{
	  if(x[mx] >= 0)
	    {
	      //     cerr << mx << endl;
	      s += x[mx];
	      for(int v : vec)
		x[v] -= x[lca(v, mx)];

	      for(int v : vec2)
		x[v] -= x[lca(v, mx)];
	      
	      int cur = mx;
	      while(x[cur] != 0)
		x[cur] = 0, cur = p[cur];
	      
	    }
	  else
	    {
	      if(child[mx].empty())
		vec2.push_back(mx);
	      
	      for(int c : child[mx])
		x[c] += x[mx];
	    }

	  for(int c : child[mx])
	    vec.push_back(c);
	}
    }
  for(int v : vec2)
    if(x[v] >= 0) s += x[v];
  cout << s - init << endl;
  return 0; 
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:105:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |       for(int i = 0; i < vec.size(); i++)
      |                      ~~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31