QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#20674 | #2426. The Xana coup | Alinxester | 0 | 15ms | 13936kb | C++14 | 2.2kb | 2022-02-17 15:30:14 | 2022-05-03 11:05:45 |
Judging History
answer
#include<bits/stdc++.h>
#define Alinxester qwq
#define int long long
#define N ((int)1e5+2)
using namespace std;
namespace STD{
inline int read(){
int s=0,t=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*t;
}
inline void write(int x){
if(x<0) x=~(x-1),putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void swap(int &a,int &b){a^=b^=a^=b;}
inline int min(int a,int b){return ((a<b)?a:b);}
inline int max(int a,int b){return ((a>b)?a:b);}
struct Pair{int fir,sec;};
inline bool Pair_cmp(Pair x,Pair y){
if(x.fir==y.fir) return x.sec<y.sec;
return x.fir<y.fir;
}
#define EDGE_N ((int)2e5+2)
#define INF ((int)1e18+2)
struct Edge{int to,next,dis;}edge[EDGE_N];
int head[EDGE_N],pos;
inline void add_edge(int u,int v,int w){edge[++pos]=(Edge){v,head[u],w},head[u]=pos;}
inline void add_edge(int u,int v){edge[++pos]=(Edge){v,head[u],0},head[u]=pos;}
inline void pre_max_0(int *a,int len){for(int i=0;i<len;++i) a[i]=INF;}
inline void pre_min_0(int *a,int len){for(int i=0;i<len;++i) a[i]=-INF;}
inline void pre_max(int *a,int len){for(int i=1;i<=len;++i) a[i]=INF;}
inline void pre_min(int *a,int len){for(int i=1;i<=len;++i) a[i]=-INF;}
}
using namespace STD;
int n,col[N],ans;
int f[N][2][2],g[N][2][2],h[2][2];
inline void dfs(int u,int fa){
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
g[u][i][j]=INF;
g[u][0][0]=g[u][1][0]=0;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(v==fa) continue;
dfs(v,u);
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
h[j][k]=g[u][j][k];
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
g[u][j][k]=min(h[j][k]+f[v][0][j],h[j][1-k]+f[v][1][j]);
}
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
f[u][j][col[u]^j^k]=g[u][j][k]+j;
}
signed main(){
n=read();
int u,v;
for(int i=1;i<n;++i) u=read(),v=read(),add_edge(u,v);
for(int i=1;i<=n;++i) col[i]=read();
for(int i=0;i<N;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
f[i][j][k]=INF;
dfs(1,0);
ans=min(f[1][0][0],f[1][1][0]);
if(ans>n) return printf("impossible\n"),0;
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Accepted
Test #1:
score: 0
Accepted
time: 2ms
memory: 11848kb
input:
5 1 2 1 3 2 4 2 5 0 1 0 1 1
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 11784kb
input:
5 1 2 2 3 3 4 4 5 0 1 1 1 1
output:
impossible
result:
ok single line: 'impossible'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #3:
score: 0
Wrong Answer
time: 4ms
memory: 9764kb
input:
17 2 7 3 17 9 16 15 8 6 13 7 10 12 17 12 4 1 11 7 15 3 14 11 17 8 17 1 5 13 7 8 16 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
output:
2
result:
wrong answer 1st lines differ - expected: '8', found: '2'
Subtask #3:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 2ms
memory: 11844kb
input:
33 6 4 25 31 28 6 9 12 16 22 27 3 11 26 27 19 28 15 10 15 23 20 11 14 28 24 24 5 33 26 8 9 4 14 1 7 22 20 27 17 13 28 19 32 23 29 10 19 18 22 21 7 21 9 30 20 2 5 29 31 31 4 21 26 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1
output:
0
result:
wrong answer 1st lines differ - expected: '13', found: '0'
Subtask #4:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 13ms
memory: 13936kb
input:
99481 19117 19116 39650 39651 69914 69913 6831 6830 32628 32629 47585 47586 9962 9963 43561 43562 65038 65037 89192 89191 55315 55314 67819 67820 62853 62852 37838 37839 13481 13482 79553 79552 13649 13648 42022 42023 40952 40953 53979 53980 31280 31281 52472 52473 4690 4691 659 660 34413 34412 6409...
output:
0
result:
wrong answer 1st lines differ - expected: '49772', found: '0'
Subtask #5:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 15ms
memory: 13896kb
input:
89310 15556 57000 19677 35349 9259 25855 43787 63864 64941 54366 20524 82369 74758 65181 26075 75148 76809 29415 64603 77798 60446 1000 86747 70876 65376 11036 2506 88761 45097 50529 45097 83913 33059 79620 54248 11298 37025 18974 7782 83068 63113 70024 69926 54332 21966 1572 79769 72650 24200 8844 ...
output:
0
result:
wrong answer 1st lines differ - expected: 'impossible', found: '0'
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%