# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1097672 | vjudge1 | The Xana coup (BOI21_xanadu) | C++14 | 66 ms | 17240 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,a[MAXN],tot,head[MAXN];
int dp[MAXN][2][2],f[MAXN][2][2],rt=1,siz[MAXN];
struct node{
int nxt,to;
}e[MAXN*4];
void add(int x,int y){
e[++tot].nxt=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fa){
//dp i 0/1 0/1 表示第i个节点 对父节点影响 相等/取反
dp[x][0][0]=0;
dp[x][1][1]=1;
dp[x][1][0]=inf;
dp[x][0][1]=inf;
int as,bs,cs,ds;
for(int i=head[x];i;i=e[i].nxt){
int to=e[i].to;
if(to==fa)continue;
dfs(to,x);
as=min(dp[x][0][0]+dp[to][0][a[to]],dp[x][0][1]+dp[to][1][a[to]]);
bs=min(dp[x][0][1]+dp[to][0][a[to]],dp[x][0][0]+dp[to][1][a[to]]);
cs=min(dp[x][1][0]+dp[to][0][!a[to]],dp[x][1][1]+dp[to][1][!a[to]]);
ds=min(dp[x][1][1]+dp[to][0][!a[to]],dp[x][1][0]+dp[to][1][!a[to]]);
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |