Submission #991366

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
991366	2024-06-02 07:44:57	12345678	The Xana coup (BOI21_xanadu)	C++17	100 / 100	45 ms	18616 KiB

xanadu

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 <bits/stdc++.h>
using namespace std;
const int nx=1e5+5, inf=1e9;
int n, a[nx], u, v, dp[nx][2][2], tmp[2][2];
vector<int> d[nx];
void dfs(int u, int p)
{
    int dp2[2][2];
    dp2[0][0]=dp2[1][0]=0;
    dp2[0][1]=dp2[1][1]=inf;
    for (auto v:d[u])
    {
        if (v==p) continue;
        dfs(v, u);
        tmp[0][0]=min(dp2[0][0]+dp[v][0][0], dp2[0][1]+dp[v][0][1]);
        tmp[0][1]=min(dp2[0][1]+dp[v][0][0], dp2[0][0]+dp[v][0][1]);
        tmp[1][0]=min(dp2[1][0]+dp[v][1][0], dp2[1][1]+dp[v][1][1]);
        tmp[1][1]=min(dp2[1][1]+dp[v][1][0], dp2[1][0]+dp[v][1][1]);
        for (int i=0; i<2; i++) for (int j=0; j<2; j++) dp2[i][j]=min(inf, tmp[i][j]);
        //cout<<"dp "<<v<<' '<<u<<' '<<dp2[0][0]<<' '<<dp2[0][1]<<' '<<dp2[1][0]<<' '<<dp2[1][1]<<'\n';
    }
    //cout<<"dp "<<u<<' '<<dp2[0][0]<<' '<<dp2[0][1]<<' '<<dp2[1][0]<<' '<<dp2[1][1]<<'\n';
    if (a[u])
    {
        dp[u][0][0]=min(inf, dp2[1][0]);
        dp[u][0][1]=min(inf, dp2[0][1]+1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40
• Subtask 5: 30 / 30