Submission #1068273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068273		jerzyk	Closing Time (IOI23_closing)	C++17	8 / 100	90 ms	38480 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];
bool vis[2][N], chk[2][N];
vector<pair<int, ll>> ed[N];

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

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;
        k += q.top().st;
        v = q.top().nd.st; r = q.top().nd.nd;
        //cerr << v << " " << r << " " << dis[r][v] << "\n";
        q.pop();
        vis[r][v] = true;
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(vis[r][ed[v][i].st]) continue;

            q.push(make_pair(-dis[r][ed[v][i].st], make_pair(ed[v][i].st, r)));
        }
    }
    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);

    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