Submission #1064607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064607		Misha_Yuzvik	Jobs (BOI24_jobs)	C++14	43 / 100	2047 ms	73048 KiB

Main

# include <bits/stdc++.h>
using namespace std;
# define For(i , l , r) for(long long i = (l); i <= (r); i++)
# define Rep(i , n) For(i , 0 , (n) - 1)
# define size(x) (long long)x.size()
# define MAXN 500005
# define MAXK 1000005
# define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll inf = 1e7 + 7;
const ll mod = 1e9 + 9;
const ld eps = 0.0000001;
ll n , m , K , ans = 0 , q , finish;
vector<vector<ll> >g(MAXN);
vector<ll>val(MAXN);
vector<ll>root(MAXN);
multiset<pair<ll , ll> >stv[MAXN];
void init(ll N) {
    For (i , 0 , N) {
        root[i] = i;
    }
}
ll get_r(ll x) {
    if (root[x] == x) return x;
    else return root[x] = get_r(root[x]);
}
void check(multiset<pair<ll , ll> >&st) {
    ll prev = -1e18;
    for (auto it = st.begin(); it != st.end(); it++) {
           if (it->first < prev) assert(0);
           if (it->first < 0 || it->second < 0) assert(0);
           prev = it->second;
    }
}
void insert_pair(multiset<pair<ll , ll> >&st , ll ai , ll bi) {
         if (size(st) == 0) {
              st.insert({ai , bi});
              return;
         }
         auto it = st.lower_bound({ai , -1e18});
         auto itl = it , itr = it;
         if (it != st.begin()) {
             it--;
             if (it->second >= ai) {
                itl = it;
                bi = bi - ai + it->second; 
                ai = it->first; // kurwa
             }
             it++;
         }
         while (it != st.end() && it->first <= bi) {
             bi = bi - it->first + it->second;
             it++;
         }
         itr = it;
         if (itl != itr) st.erase(itl , itr);
         st.insert({ai , bi});
         check(st);
}
ll Union(ll x , ll y) {
    ll r1 = get_r(x) , r2 = get_r(y);
    if (r1 == r2) assert(0);
    if (size(stv[r1]) > size(stv[r2])) swap(r1 , r2);
    root[r2] = r1;
    auto& st = stv[r1];
    for (auto [ai , bi] : stv[r2]) {
         insert_pair(st , ai , bi);
    }
    return r1;
}
void dfs(ll v , ll p) {
       pair<ll , ll>cur;
       if (val[v] < 0) cur = {abs(val[v]) , 0};
       else cur = {0 , val[v]};
       ll rv = -1;
       for (auto to : g[v]) {
            if (to == p) continue;
            dfs(to , v);
            if (rv == -1) rv = get_r(to);
            else rv = Union(rv , to);
       }
       if (rv == -1) {
            if (val[v] > 0) {
                  insert_pair(stv[v] , cur.first , cur.second);
            }
            return;
       }
       auto &st = stv[rv];
       root[v] = rv;
       if (val[v] > 0) {
           insert_pair(st , cur.first , cur.second);
       }  else if (val[v] < 0) {
           while (size(st) > 0 && cur.first >= cur.second) {
                 auto [a1 , b1] = *st.begin();
                 cur.first = cur.first - cur.second + a1;
                 cur.second = b1;
                 st.erase(st.begin());
           }
           if (cur.first < cur.second)  insert_pair(st , cur.first , cur.second);
       }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll val0;
    cin >> n >> val0;
    For (i , 1 , n) {
         ll p;
         cin >> val[i] >> p;
         g[i].push_back(p);
         g[p].push_back(i);
    }
    val[0] = val0;
    // For (i , 1 , n) cin >> val[i];
    // Rep (i , n - 1) {
    //     ll u , v;
    //     cin >> u >> v;
    //     g[u].push_back(v);
    //     g[v].push_back(u);
    // }
    // n++;
    // val[n] = 1e18;
    // g[n].push_back(finish);
    // g[finish].push_back(n);
    init(n);
    dfs(0 , -1);
    auto& wyn = stv[get_r(0)];
    ll sum = 0;
    for (auto [ai , bi] : wyn) {
          if (sum >= ai) sum = sum - ai + bi;
       //   cerr << ai << ' ' << bi << "\n";
    }
    cout << sum - val0;
   // cerr << 1 << endl;
   // if (sum >= 1e17) cout << "TAK";
   // else cout << "NIE";
}

Compilation message (stderr)

Main.cpp: In function 'll Union(ll, ll)':
Main.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for (auto [ai , bi] : stv[r2]) {
      |               ^
Main.cpp: In function 'void dfs(ll, ll)':
Main.cpp:95:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |                  auto [a1 , b1] = *st.begin();
      |                       ^
Main.cpp: In function 'int main()':
Main.cpp:130:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |     for (auto [ai , bi] : wyn) {
      |               ^

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