Submission #805304

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
805304	2023-08-03 14:58:58	Kerim	경주 (Race) (IOI11_race)	C++17	100 / 100	347 ms	122516 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "race.h"
#include "bits/stdc++.h"
#define ll long long
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5+5;
const int INF = 1e9;
vector<pii> adj[N];
int K, answer;
int dp[N][105];
void dfs(int nd, int pr){
    dp[nd][0] = 0;
    for (int i = 1; i <= K; i++)
        dp[nd][i] = INF;
    for (auto [c, e]: adj[nd]){
        if (c == pr)
            continue;
        dfs(c, nd);
        //update answer
        for (int w1 = 0; w1 + e <= K; w1++){
            int w2 = K - e - w1;
            answer = min(answer, dp[nd][w1] + dp[c][w2]+1);
        }
        //update dp
        for (int p = 0; p+e <= K; p++)
            dp[nd][p+e] = min(dp[nd][p+e],dp[c][p]+1);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57