Submission #888939

#	Time	Username	Problem	Language	Result	Execution time	Memory
888939		ZHIRDILBILDIZ	Closing Time (IOI23_closing)	C++17	0 / 100	1077 ms	57552 KiB

closing

#include<bits/stdc++.h>
#include "closing.h"
#define fi first
#define se second
#define ll long long
using namespace std;
const ll N = 2e5 + 10;
bitset<N> us;
vector<pair<ll, ll>> gr[N];
ll dist[N][2];
ll ds[N][2];
bool flag;
void ultra_clear(ll n) {
    flag &= 0;
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < 2; ++j)
            dist[i][j] &= 0,
                ds[i][j] &= 0;
        gr[i].clear();
        us[i] = 0;
    }
}
void pre_calc(ll city, ll last, ll type) {
    for (auto i : gr[city]) {
        if (i.fi == last)
            continue;
        dist[i.fi][type] = dist[city][type] + i.se;
        pre_calc(i.fi, city, type);
    }
}
void get_path(ll city, ll last, ll y, vector<ll> &path) {
    if (!flag)
        path.push_back(city);
    if (city == y) {
        flag = 1;
        return;
    }
    for (auto i : gr[city]) {
        if (i.fi == last)
            continue;
        get_path(i.fi, city, y, path);
    }
    if (!flag)
        path.pop_back();
}
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
    ultra_clear(n);
    int m = n - 1, ans = 0;
    for (ll i = 0; i < m; ++i) {
        gr[u[i]].push_back({v[i], w[i]});
        gr[v[i]].push_back({u[i], w[i]});
    }
    dist[x][0] = dist[y][1] &= 0;
    pre_calc(x, 0, 0);
    pre_calc(y, 0, 1);
    set<pair<ll, ll>> stx, sty;
    vector<ll> path;
    get_path(x, 0, y, path);
    ll psz = path.size() - 1;
    for (ll i = 0; i <= path.size(); ++i) {
        for (ll j = 0; j <= path.size(); ++j) {

            ll hp = k;
            ll cnt = 0;
            ll now[n] = {};
            bool us[n][2] = {};
            for (ll q = 0; q < n; ++q)
                ds[q][0] = dist[q][0],
                    ds[q][1] = dist[q][1];

            for (ll q = 0; q < i - 1; ++q)
                now[path[q]] = max(now[path[q]], dist[path[q]][0]);

            for (ll q = 0; q < j - 1; ++q)
                now[path[psz - q]] = max(now[path[psz - q]], dist[path[psz - q]][1]);
            for (ll q = 0; q <= psz; ++q) {
                for (ll z = 0; z < 2; ++z)
                    ds[path[q]][z] = max(0ll, ds[path[q]][z] - now[path[q]]);
                hp -= now[path[q]];
            }

            if (hp < 0)
                break;

            set<pair<ll, ll>> stx, sty;

            for (ll i = 0; i < n; ++i)
                stx.insert({ds[i][0], i}),
                    sty.insert({ds[i][1], i});
//            cout << "abu\n";
//            cout << "i = " << i << ' ' << "j = " << j <<'\n';
            while (stx.size() || sty.size()) {
                pair<ll, ll> p1 = {1e18 + 1, 1e18}, p2 = {1e18 + 1, 1e18};
                if (stx.size())
                    p1 = *stx.begin();
                if (sty.size())
                    p2 = *sty.begin();
//                cout << hp << ' ' << p1.fi << ' ' << p1.se << ' ' << p2.fi << ' ' << p2.se << '\n';
                if (p1.fi <= p2.fi) {
                    if (hp - p1.fi < 0)
                        break;
                    hp -= p1.fi;
                    us[p1.se][0] = 1;
                    if (!us[p1.se][1])
                        sty.erase({max(0ll, dist[p1.se][1] - now[p1.se]), p1.se});
                    now[p1.se] += p1.fi;
                    if (!us[p1.se][1])
                        sty.insert({max(0ll, dist[p1.se][1] - now[p1.se]), p1.se});
                    stx.erase(stx.begin());
                } else {
                    if (hp - p2.fi < 0)
                        break;
                    us[p2.se][1] = 1;
                    hp -= p2.fi;
                    if (!us[p2.se][0])
                        stx.erase({max(0ll, dist[p2.se][0] - now[p2.se]), p2.se});
                    now[p2.se] += p2.fi;
                    if (!us[p2.se][0])
                        stx.insert({max(0ll, dist[p2.se][0] - now[p2.se]), p2.se});
                    sty.erase(sty.begin());
                }
                ++cnt;
            }

            ans = max((ll)ans, cnt);
        }
    }
    return ans;
}
//signed main() {
////    ios::sync_with_stdio(0);
////    cin.tie(0); cout.tie(0);
//    int t;
//    cin >> t;
//    while (t--) {
//        int n;
//        int x, y;
//        ll k;
//        cin >> n >> x >> y >> k;
//        vector<int> u(n - 1), v(n - 1), w(n - 1);
//        for (int i = 0; i < n - 1; ++i)
//            cin >> u[i] >> v[i] >> w[i];
//        cout << max_score(n, x, y, k, u, v, w);
//    }
//    return 0;
//}
//2
//7 0 2 10
//0 1 2
//0 3 3
//1 2 4
//2 4 2
//2 5 5
//5 6 3
//4 0 3 20
//0 1 18
//1 2 1
//2 3 19

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:60: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]
   60 |     for (ll i = 0; i <= path.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~
closing.cpp:61:26: 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]
   61 |         for (ll j = 0; j <= path.size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~

• 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