Submission #1106175

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1106175	2024-10-29 13:24:08	alexdd	The Xana coup (BOI21_xanadu)	C++17	10 / 100	62 ms	16972 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 INF = 1e9;
int n;
vector<int> con[100005];
int dp[100005][2][2];//dp[nod][stare_nod][insus]
int a[100005];
void dfs(int nod, int par)
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            dp[nod][i][j]=INF;
    dp[nod][a[nod]][0]=0;
    dp[nod][1-a[nod]][1]=1;
    for(int adj:con[nod])
    {
        if(adj==par)
            continue;
        dfs(adj,nod);
        int old[2][2];
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                old[i][j]=dp[nod][i][j], dp[nod][i][j]=INF;
        for(int v=0;v<2;v++)
        {
            dp[nod][v][0] = min(old[v][0]+dp[adj][0][0], old[1-v][0]+dp[adj][0][1]);
            dp[nod][v][1] = min(old[v][1]+dp[adj][1][0], old[1-v][1]+dp[adj][1][1]);
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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