Submission #1068717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068717		jerzyk	Closing Time (IOI23_closing)	C++17	8 / 100	87 ms	45392 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;
int tab[N];
ll dis[2][N], curmi[2][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)
{
    curmi[r][v] = I;
    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;
        curmi[r][v] = min(curmi[r][v], dis[r][ed[v][i].st]);
        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";
    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)));
        }
    }
    return ans;
}

/*priority_queue<pair<ll, pair<int, int>>> qs, qd;
priority_queue<pair<ll, int>> qj;

pair<int, int> Get(ll &k)
{
    while((int)qd.size() > 0 && vis[qd.top().nd.nd][qd.top().nd.st])
        qd.pop();
    while((int)qj.size() > 0 && (vis[0][qj.top().nd] || vis[1][qj.top().nd]))
        qj.pop();
    while((int)qs.size() > 0 && vis[qs.top().nd.nd][qs.top().nd.st])
        qs.pop();
    pair<int, int> ans;
    pair<ll, pair<int, int>> v1;

}

void ChkE(int v, int r)
{
    if(chk[v][r ^ 1] && !vis[v][r ^ 1])
        qs.push(make_pair(dis[v][r] - dis[v][r ^ 1], make_pair(v, r ^ 1)));
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        chk[ed[v][i].st][r] = true;
        if(vis[ed[v][i].st][r])
        {
            if(chk[ed[v][i].st][r ^ 1] && !vis[ed[v][i].st][r ^ 1])
                qs.push(make_pair(2LL * (dis[v][r] - dis[v][r ^ 1]), make_pair(v, r ^ 1)));
            else
                curmi[ed[v][i].st][r ^ 1] = min(curmi[ed[v][i].st][r ^ 1], dis[v][r^1] - dis[v][r]);
            continue;
        }
        if(vis[ed[v][i].st][r ^ 1])
            qs.push(make_pair(dis[v][r ^ 1] - dis[v][r], make_pair(v, r)));
        else
        {
            if(chk[ed[v][i].st][r ^ 1])
                qj.push(make_pair(-dis[ed[v][i].st][r], v));
            else
            {
                qd.push(make_pair(-dis[ed[v][i].st][r] - curmi[ed[v][i].st][r], make_pair(ed[v][i].st, r)));
                qs.push(make_pair(-dis[ed[v][i].st][r], make_pair(v, r)));
            }
        }
    }
}

void PthA(int n, int x, int y, ll k)
{
    int v, r, ans, xd = 0;
    pair<int, int> curv;
    DFSP(x, y, 0);
    for(int i = 0; i < (int)pth.size(); ++i)
    {
        k -= min(dis[0][pth[i]], dis[1][pth[i]]);
        if(dis[0][pth[i]] <= dis[1][pth[i]])
            vis[0][pth[i]] = true;
        else
        {
            if(xd == 0)
            {
                chk[pth[i]][0] = true;
                chk[pth[i - 1]][1] = true;
            }
            vis[1][pth[i]] = true;
        }
    }
    if(k < 0) return 0;
    for(int i = 0; i < (int)pth.size(); ++i)
        if(dis[0][pth[i]] <= dis[1][pth[i]])
            ChkE(pth[i], 0);
        else
            ChkE(pth[i], 1);
    ans = (int)pth.size();
    while()
}*/

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);

    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