답안 #840815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840815 2023-08-31T17:44:58 Z MohamedAliSaidane 봉쇄 시간 (IOI23_closing) C++17
9 / 100
415 ms 1084648 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 1084560 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 64 ms 4984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -