Submission #1069345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069345		jerzyk	Closing Time (IOI23_closing)	C++17	8 / 100	100 ms	39368 KiB

closing

#include <bits/stdc++.h>
#include "closing.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
ll dis[2][N];
ll tab[N][2];
int cnt[N];
bool vis[2][N], chk[2][N];
vector<pair<int, ll>> ed[N];
vector<int> pth;

inline void Clean(int n)
{
    for(int i = 0; i < n; ++i)
    {
        ed[i].clear();
        vis[0][i] = false; vis[1][i] = false;
        chk[0][i] = false; chk[1][i] = false;
    }
}

void DFSD(int v, int r)
{
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(dis[r][ed[v][i].st] <= dis[r][v]) continue;
        dis[r][ed[v][i].st] = dis[r][v] + ed[v][i].nd;

        DFSD(ed[v][i].st, r);
    }
}

bool DFSP(int v, int tar, int o)
{
    if(v == tar)
    {
        pth.pb(v); return true;
    }
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(ed[v][i].st == o) continue;
        if(DFSP(ed[v][i].st, tar, v))
        {
            pth.pb(v); return true;
        }
    }
    return false;
}

int Norm(int n, int x, int y, ll k)
{
    //cerr << "Norm: \n";
    pth.clear();
    int v, r, ans = 0;
    priority_queue<pair<ll, pair<int, int>>> q;
    q.push(make_pair(0, make_pair(x, 0)));
    q.push(make_pair(0, make_pair(y, 1)));
    //cerr << x << " " << y << "\n";
    while((int)q.size() > 0 && -q.top().st <= k)
    {
        ++ans;
        ll xd = q.top().st;
        v = q.top().nd.st; r = q.top().nd.nd;
        q.pop();
        if(vis[r][v]) continue;
        k += xd;
        //cerr << v << " " << r << " " << dis[r][v] << "\n";
        vis[r][v] = true;
        if(!vis[r ^ 1][v] && chk[r ^ 1][v]) q.push(make_pair(dis[r][v] - dis[r ^ 1][v], make_pair(v, r ^ 1)));

        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(vis[r][ed[v][i].st]) continue;
            chk[r][ed[v][i].st] = true;
            q.push(make_pair(-dis[r][ed[v][i].st], make_pair(ed[v][i].st, r)));
        }
    }
    for(int i = 0; i < n; ++i)
    {
        vis[0][i] = false; vis[1][i] = false;
        chk[0][i] = false; chk[1][i] = false;
    }
    return ans;
}

int PthA(int n, int x, int y, ll k)
{
    //cerr << "Pth\n";
    int ans, v;
    ll val;
    priority_queue<pair<ll, int>> q1, q2;
    DFSP(x, y, 0);
    for(int i = 0; i < n; ++i)
    {
        tab[i][0] = min(dis[0][i], dis[1][i]);
        tab[i][1] = max(dis[0][i], dis[1][i]) - tab[i][0];
    }
    for(int i = 0; i < (int)pth.size(); ++i)
    {
        k -= min(dis[0][pth[i]], dis[1][pth[i]]);
        ++cnt[pth[i]];
    }
    if(k < 0LL) return 0;
    ans = pth.size();
    for(int i = 0; i < n; ++i)
    {
        if(cnt[i] == 0)
            q2.push(make_pair(-tab[i][0] - tab[i][1], i));
        q1.push(make_pair(-tab[i][cnt[i]], i));
    }
    ll cst = I;
    while(k > 0 && (int)q1.size() > 0)
    {
        v = q1.top().nd;
        val = -q1.top().st;
        q1.pop();
        while((int)q1.size() > 0 && cnt[q1.top().nd] > 1) q1.pop();
        cst = I;
        if((int)q1.size() == 0 || (int)q2.size() == 0 || -q2.top().st > k || -q1.top().st + val <= -q2.top().st)
        {
            if(val > k) break;
            if((int)q2.size() > 0) cst = -q2.top().nd - val;

            k -= val; ++ans;
            ++cnt[v];
            if(cnt[v] < 2) q1.push(make_pair(-tab[v][1], v));
        }else
        {
            q1.push(make_pair(-val, v));
            v = q2.top().nd; val = -q2.top().st;
            q2.pop();
            
            cnt[v] = 2;
            ans += 2;
            k -= val;
        }
        while((int)q1.size() > 0 && cnt[q1.top().nd] > 1) q1.pop();
        while((int)q2.size() > 0 && cnt[q2.top().nd] > 0) q2.pop();
    }
    if(cst <= k) ++ans;
    return ans;
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W)
{
    int n = N, u = X, v = Y, answer;
    //cerr << "xd " << X << " " << Y << "\n";
    for(int i = 0; i < n - 1; ++i)
    {
        ed[U[i]].pb(make_pair(V[i], W[i]));
        ed[V[i]].pb(make_pair(U[i], W[i]));
    }
    for(int j = 0; j < 2; ++j)
        for(int i = 0; i < n; ++i)
            dis[j][i] = I;
    dis[0][u] = 0LL; dis[1][v] = 0LL;
    DFSD(u, 0); DFSD(v, 1);
    //cerr << "xd\n";
    answer = Norm(n, u, v, K);
    answer = max(answer, PthA(n, u, v, K));
    Clean(n);
    return answer;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 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