Submission #1087981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087981		Valaki2	Closing Time (IOI23_closing)	C++17	0 / 100	1043 ms	32476 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 2e5;

struct edge {
    int to, wei;
};

int ans;

int n, x, y, k;
vector<pii > g[1 + maxn];
int d[2][1 + maxn];
bool done[2][1 + maxn];

void dfs(int cur, int idx, int par) {
    for(pii nei : g[cur]) {
        if(nei.fi != par) {
            d[idx][nei.fi] = d[idx][cur] + nei.se;
            dfs(nei.fi, idx, cur);
        }
    }
}

struct item {
    int val;
    int pos;
    int type;
    bool operator < (const item & other) const {
        return val > other.val;
    }
};

int sum, cur_ans;
priority_queue<item> q;

void push_for(item cur) {
    for(pii nei : g[cur.pos]) {
        if(!done[cur.type][nei.fi]) {
            if(!done[cur.type^1][nei.fi]) {
                q.push({d[cur.type][nei.fi], nei.fi, cur.type});
            } else {
                q.push({max(0ll, d[cur.type][nei.fi] - d[cur.type^1][nei.fi]), nei.fi, cur.type});
            }
        }
    }
}

bool topush;

bool eval(item cur) {
    if(done[cur.type][cur.pos]) {
        return true;
    }
    if(cur.val > k - sum) {
        return false;
    }
    sum += cur.val;
    cur_ans++;
    done[cur.type][cur.pos] = true;
    if(topush) {
        push_for(cur);
    }
    return true;
}

vector<int> path;

bool path_dfs(int cur, int par) {
    if(cur == y) {
        path.pb(y);
        return true;
    }
    for(pii nei : g[cur]) {
        if(nei.fi != par) {
            bool res = path_dfs(nei.fi, cur);
            if(res) {
                path.pb(cur);
                return true;
            }
        }
    }
    return false;
}

bool do_this(int i, int type, bool inc) {
    if(type == 0) {
        int bound = i - 1;
        if(inc) {
            bound = i;
        }
        for(int j = 0; j <= bound; j++) {
            if(!eval({d[type][path[j]], path[j], type})) {
                return false;
            }
        }
    } else { // this might be wrong !!!!!
        int bound = i + 1;
        if(inc) {
            bound = i;
        }
        for(int j = path.size() - 1; j >= bound; j--) {
            if(!eval({d[type][path[j]], path[j], type})) {
                return false;
            }
        }
    }
    return true;
}

int thing[1 + maxn];

void inc(int idx, int type) {
    int newval = max(thing[idx], d[type][idx]);
    sum += newval - thing[idx];
    thing[idx] = newval;
    cur_ans++;
}

void solve() {
    dfs(x, 0, -1);
    dfs(y, 1, -1);
    for(int i = x; i <= n; i++) {
        sum = 0, cur_ans = 0;
        for(int j = 1; j <= n; j++) {
            thing[j] = 0;
        }
        for(int j = x; j <= min(y - 1, i); j++) {
            inc(j, 0);
        }
        for(int j = y; j <= i; j++) {
            inc(j, 1);
            inc(j, 0);
        }
        for(int j = y; j >= 1; j--) {
            if(j != y) {
                if(j >= x) {
                    inc(j, 1);
                } else {
                    inc(j, 0);
                    inc(j, 1);
                }
            }
            if(sum > k) {
                break;
            }
            /*for(int l = y - 1; l >= max(j, x); l--) {
                inc(l, 1);
            }
            for(int l = x - 1; l >= j; l--) {
                inc(l, 0);
                inc(l, 1);
            }*/
            vector<int> v;
            for(int l = 1; l < min(x, j); l++) {
                v.pb(d[0][l]);
            }
            for(int l = max(i, y) + 1; l <= n; l++) {
                v.pb(d[1][l]);
            }
            sort(v.begin(), v.end());
            int extra = 0; int extra_sum = 0;
            for(int tmp : v) {
                if(tmp + sum + extra_sum <= k) {
                    extra_sum += tmp;
                    extra++;
                }
            }
            cur_ans += extra;
            ans = max(ans, cur_ans);
            cur_ans -= extra;
        }
    }
    q.push({0, x, 0});
    q.push({0, y, 1});
    topush = true;
    sum = 0, cur_ans = 0;
    while(!q.empty()) {
        item cur = q.top();
        q.pop();
        bool res = eval(cur);
        if(!res) {
            break;
        }
    }
    ans = cur_ans;
    path_dfs(x, -1);
    reverse(path.begin(), path.end());
    for(int i = 0; i < path.size(); i++) {
        for(int i = 1; i <= n; i++) {
            done[0][i] = done[1][i] = false;
        }
        sum = 0, cur_ans = 0;
        while(!q.empty()) {
            q.pop();
        }
        topush = false;
        if(d[0][path[i]] < d[1][path[i]]) {
            if(!do_this(i, 0, true)) {
                continue;
            }
            if(!do_this(i, 1, false)) {
                continue;
            }
            if(!eval({d[1][path[i]] - d[0][path[i]], path[i], 1})) {
                continue;
            }
        } else {
            if(!do_this(i, 1, true)) {
                continue;
            }
            if(!do_this(i, 0, false)) {
                continue;
            }
            if(!eval({d[0][path[i]] - d[1][path[i]], path[i], 0})) {
                continue;
            }
        }
        while(!q.empty()) {
            q.pop();
        }
        topush = true;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 2; j++) {
                if(done[j][i]) {
                    push_for({-1, i, j});
                }
            }
        }
        while(!q.empty()) {
            item cur = q.top();
            q.pop();
            bool res = eval(cur);
            if(!res) {
                break;
            }
        }
        ans = max(ans, cur_ans);
    }
}

void reset() {
    ans = 0;
    for(int i = 1; i <= n; i++) {
        g[i].clear();
        d[0][i] = d[1][i] = 0;
        done[0][i] = done[1][i] = false;
        thing[i] = 0;
    }
    sum = 0, cur_ans = 0;
    while(!q.empty()) {
        q.pop();
    }
    path.clear();
    //
}

signed max_score(signed N, signed X, signed Y, int K,
              vector<signed> U, vector<signed> V, vector<signed> W) {
    reset();
    n = N, x = X, y = Y, k = K;
    x++;
    y++;
    for(int i = 0; i < n - 1; i++) {
        int a = U[i], b = V[i], c = W[i];
        a++;
        b++;
        g[a].pb(mp(b, c));
        g[b].pb(mp(a, c));
    }
    solve();
    return ans;
}

Compilation message (stderr)

closing.cpp: In function 'void solve()':
closing.cpp:198:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     for(int i = 0; i < path.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17