Submission #840815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840815	2023-08-31T17:44:58 Z	MohamedAliSaidane	Closing Time (IOI23_closing)	C++17	9 / 100	415 ms	1084648 KB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

typedef  __int128 ll;

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(),(x).end()

const int nax = 205;
const ll INF = 1e18 + 2;

int n, x, y;
ll k;
vector<pair<int,ll>> A[nax];
vector<int> adj[nax];
ll dx[nax], dy[nax];
ll dp[nax][2 * nax][4], memo[nax][2 * nax][4][nax];
int tx[nax], ty[nax];

void dfsx(int u, int par)
{
    for(auto e: A[u])
    {
        if(e.ff == par)
            continue;
        dx[e.ff] = dx[u] + e.ss;
        tx[e.ff] = u;
        dfsx(e.ff, u);
    }
}
void dfsy(int u, int par)
{
    for(auto e: A[u])
    {
        if(e.ff == par)
            continue;
        dy[e.ff] = dy[u] + e.ss;
        ty[e.ff] = u;
        dfsy(e.ff, u);
    }
}
ll f(int u, int ans, int typ);

ll g(int u, int rem, int typ, int idx)
{
    if(rem < 0)
        return INF;
    if(idx == (int)(adj[u].size()))
        return rem > 0? INF: 0ll;
    if(memo[u][rem][typ][idx] != -1)
        return memo[u][rem][typ][idx];
    if(rem == 0)
        return memo[u][rem][typ][idx] = 0ll;
    ll rep = INF;
    for(int j = 0; j <= rem; j++)
    {
        if(typ == 0)
        {
            if(adj[u][idx] == ty[u])
                rep = min(rep, g(u, rem-j, typ, idx + 1) + f(adj[u][idx], j - 1, 2));
            rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j, 0));
        }
        else if(typ == 1)
        {
            rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j - 1, 1));
            rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j, 0));
            if(ty[u] == adj[u][idx])
            {
                rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j - 1, 2));
                rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j - 2, 3));
            }
        }
        else if(typ == 2)
        {
            rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j - 1, 2));
            if(ty[u] != adj[u][idx])
                rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j, 0));
        }
        else 
        {
            rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j - 2, 3));
            rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j - 1, 2));
            if(ty[u] != adj[u][idx])
            {
                rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j - 1, 1));
                rep = min(rep, g(u, rem - j, typ, idx + 1) + f(adj[u][idx], j, 0));
            }
        }
    }
    return memo[u][rem][typ][idx] = rep;
}
ll f(int u, int ans, int typ)
{
    if(ans < 0)
        return INF;
    if(dp[u][ans][typ] != -1)
        return dp[u][ans][typ];
    ll deplt = typ == 0? 0: typ == 1? dx[u]: typ == 2? dy[u]: max(dx[u], dy[u]);
    if(adj[u].empty())
        return dp[u][ans][typ] = ans > 0? INF: deplt;
    
    return dp[u][ans][typ] = g(u, ans, typ, 0)  + deplt;
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = N, x = X, y = Y, k = K;
    for(int i = 0; i < N; i ++)
    {
        A[i].clear();
        adj[i].clear();
    }
    memset(dp, -1, sizeof(dp));
    memset(memo, -1, sizeof(memo));
    for(int i = 0; i < n - 1; i++)
    {
        A[U[i]].pb({V[i], W[i]});
        A[V[i]].pb({U[i], W[i]});
    }
    tx[x] = x, ty[y] = y;
    dx[x] = dy[y] = 0ll;
    dfsx(x, x);
    dfsy(y, y);
    for(int i = 0; i < n; i++)
    {
        vector<int> v;
        for(auto e: A[i])
            if(e.ff != tx[i])
                adj[i].pb(e.ff);
    }
    for(int ans = 2; ans <= 2 * n; ans++)
    {
        ll cost = INF;
        cost = min(cost, f(x, ans, 0));
        cost = min(cost, f(x, ans - 1, 1));
        cost = min(cost, f(x, ans - 1, 2));
        cost = min(cost, f(x, ans - 2, 3));
        if(cost > k)
            return ans - 1;
    }
    
    return 2 * n;
}

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	415 ms	1084560 KB	Output is correct

Subtask #1
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	64 ms	4984 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	320 ms	1084496 KB	Output is correct
2	Correct	344 ms	1084500 KB	Output is correct
3	Correct	315 ms	1084464 KB	Output is correct
4	Correct	310 ms	1084536 KB	Output is correct
5	Correct	305 ms	1084556 KB	Output is correct
6	Correct	334 ms	1084540 KB	Output is correct
7	Correct	321 ms	1084484 KB	Output is correct
8	Correct	343 ms	1084576 KB	Output is correct
9	Correct	323 ms	1084528 KB	Output is correct
10	Incorrect	320 ms	1084456 KB	1st lines differ - on the 1st token, expected: '44', found: '52'
11	Halted	0 ms	0 KB	-

Subtask #3
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	320 ms	1084496 KB	Output is correct
2	Correct	344 ms	1084500 KB	Output is correct
3	Correct	315 ms	1084464 KB	Output is correct
4	Correct	310 ms	1084536 KB	Output is correct
5	Correct	305 ms	1084556 KB	Output is correct
6	Correct	334 ms	1084540 KB	Output is correct
7	Correct	321 ms	1084484 KB	Output is correct
8	Correct	343 ms	1084576 KB	Output is correct
9	Correct	323 ms	1084528 KB	Output is correct
10	Incorrect	320 ms	1084456 KB	1st lines differ - on the 1st token, expected: '44', found: '52'
11	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	320 ms	1084496 KB	Output is correct
2	Correct	344 ms	1084500 KB	Output is correct
3	Correct	315 ms	1084464 KB	Output is correct
4	Correct	310 ms	1084536 KB	Output is correct
5	Correct	305 ms	1084556 KB	Output is correct
6	Correct	334 ms	1084540 KB	Output is correct
7	Correct	321 ms	1084484 KB	Output is correct
8	Correct	343 ms	1084576 KB	Output is correct
9	Correct	323 ms	1084528 KB	Output is correct
10	Incorrect	320 ms	1084456 KB	1st lines differ - on the 1st token, expected: '44', found: '52'
11	Halted	0 ms	0 KB	-

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	415 ms	1084560 KB	Output is correct
2	Correct	320 ms	1084496 KB	Output is correct
3	Correct	344 ms	1084500 KB	Output is correct
4	Correct	315 ms	1084464 KB	Output is correct
5	Correct	310 ms	1084536 KB	Output is correct
6	Correct	305 ms	1084556 KB	Output is correct
7	Correct	304 ms	1084484 KB	Output is correct
8	Correct	321 ms	1084500 KB	Output is correct
9	Correct	308 ms	1084460 KB	Output is correct
10	Correct	314 ms	1084548 KB	Output is correct
11	Correct	327 ms	1084508 KB	Output is correct
12	Correct	315 ms	1084484 KB	Output is correct
13	Correct	311 ms	1084508 KB	Output is correct
14	Correct	311 ms	1084644 KB	Output is correct
15	Correct	305 ms	1084480 KB	Output is correct
16	Correct	311 ms	1084648 KB	Output is correct
17	Correct	313 ms	1084448 KB	Output is correct
18	Correct	310 ms	1084488 KB	Output is correct
19	Correct	307 ms	1084600 KB	Output is correct
20	Correct	324 ms	1084440 KB	Output is correct
21	Correct	309 ms	1084540 KB	Output is correct
22	Correct	307 ms	1084452 KB	Output is correct
23	Correct	310 ms	1084496 KB	Output is correct
24	Correct	306 ms	1084460 KB	Output is correct

Subtask #6
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	415 ms	1084560 KB	Output is correct
2	Correct	320 ms	1084496 KB	Output is correct
3	Correct	344 ms	1084500 KB	Output is correct
4	Correct	315 ms	1084464 KB	Output is correct
5	Correct	310 ms	1084536 KB	Output is correct
6	Correct	305 ms	1084556 KB	Output is correct
7	Correct	334 ms	1084540 KB	Output is correct
8	Correct	321 ms	1084484 KB	Output is correct
9	Correct	343 ms	1084576 KB	Output is correct
10	Correct	323 ms	1084528 KB	Output is correct
11	Incorrect	320 ms	1084456 KB	1st lines differ - on the 1st token, expected: '44', found: '52'
12	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	415 ms	1084560 KB	Output is correct
2	Correct	320 ms	1084496 KB	Output is correct
3	Correct	344 ms	1084500 KB	Output is correct
4	Correct	315 ms	1084464 KB	Output is correct
5	Correct	310 ms	1084536 KB	Output is correct
6	Correct	305 ms	1084556 KB	Output is correct
7	Correct	334 ms	1084540 KB	Output is correct
8	Correct	321 ms	1084484 KB	Output is correct
9	Correct	343 ms	1084576 KB	Output is correct
10	Correct	323 ms	1084528 KB	Output is correct
11	Incorrect	320 ms	1084456 KB	1st lines differ - on the 1st token, expected: '44', found: '52'
12	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	415 ms	1084560 KB	Output is correct
2	Correct	320 ms	1084496 KB	Output is correct
3	Correct	344 ms	1084500 KB	Output is correct
4	Correct	315 ms	1084464 KB	Output is correct
5	Correct	310 ms	1084536 KB	Output is correct
6	Correct	305 ms	1084556 KB	Output is correct
7	Correct	334 ms	1084540 KB	Output is correct
8	Correct	321 ms	1084484 KB	Output is correct
9	Correct	343 ms	1084576 KB	Output is correct
10	Correct	323 ms	1084528 KB	Output is correct
11	Incorrect	320 ms	1084456 KB	1st lines differ - on the 1st token, expected: '44', found: '52'
12	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	415 ms	1084560 KB	Output is correct
2	Correct	320 ms	1084496 KB	Output is correct
3	Correct	344 ms	1084500 KB	Output is correct
4	Correct	315 ms	1084464 KB	Output is correct
5	Correct	310 ms	1084536 KB	Output is correct
6	Correct	305 ms	1084556 KB	Output is correct
7	Correct	334 ms	1084540 KB	Output is correct
8	Correct	321 ms	1084484 KB	Output is correct
9	Correct	343 ms	1084576 KB	Output is correct
10	Correct	323 ms	1084528 KB	Output is correct
11	Incorrect	320 ms	1084456 KB	1st lines differ - on the 1st token, expected: '44', found: '52'
12	Halted	0 ms	0 KB	-

Submission #840815

Compilation message