oj.uz

Submission #1068273

# Submission time Handle Problem Language Result Execution time Memory
1068273 2024-08-21T09:00:25 Z jerzyk Closing Time (IOI23_closing) C++17
8 / 100
 90 ms 38480 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 32840 KB Output is correct
2 Correct 90 ms 38480 KB Output is correct
3 Correct 43 ms 11600 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Incorrect 3 ms 6492 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Incorrect 3 ms 6492 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Incorrect 3 ms 6492 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -