QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#20676	#2426. The Xana coup	Alinxester	30	27ms	21988kb	C++14	2.2kb	2022-02-17 15:33:55	2022-05-03 11:05:51

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-05-03 11:05:51]
评测

测评结果：30
用时：27ms
内存：21988kb

查看

[2022-02-17 15:33:55]
提交

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),add_edge(v,u);
	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;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Accepted

Test #1:

score: 0

Accepted

time: 3ms

memory: 11844kb

input:

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 1ms

memory: 11888kb

input:

output:

impossible

result:

ok single line: 'impossible'

Subtask #2:

score: 5

Accepted

Dependency #1:

100%

Accepted

Test #3:

score: 5

Accepted

time: 5ms

memory: 11840kb

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:

result:

ok single line: '8'

Test #4:

score: 0

Accepted

time: 5ms

memory: 9856kb

input:

14
5 13
4 1
2 1
7 2
6 14
10 14
12 3
2 6
5 11
12 2
6 8
10 11
12 9
1 1 1 0 1 1 0 1 0 1 0 1 0 1

output:

result:

ok single line: '10'

Test #5:

score: 0

Accepted

time: 1ms

memory: 9844kb

input:

20
11 12
8 7
18 5
6 8
2 9
17 7
19 10
1 5
2 11
18 20
14 13
15 4
13 11
16 11
12 10
15 13
1 13
20 3
13 8
0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1

output:

result:

ok single line: '6'

Test #6:

score: 0

Accepted

time: 5ms

memory: 11848kb

input:

20
5 6
18 6
9 12
18 16
10 15
18 8
3 10
3 17
16 15
12 11
10 1
10 14
20 13
17 20
6 4
7 17
5 19
13 2
12 2
1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0

output:

result:

ok single line: '11'

Test #7:

score: 0

Accepted

time: 5ms

memory: 11904kb

input:

20
8 10
2 20
13 8
16 17
6 16
15 11
2 16
18 8
4 14
10 19
9 1
3 6
4 5
12 2
13 5
7 1
13 7
15 16
17 1
0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 0 0

output:

impossible

result:

ok single line: 'impossible'

Subtask #3:

score: 15

Accepted

Test #8:

score: 15

Accepted

time: 0ms

memory: 11860kb

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:

result:

ok single line: '13'

Test #9:

score: 0

Accepted

time: 1ms

memory: 11816kb

input:

39
26 9
26 14
28 25
18 38
6 15
1 28
23 31
20 3
17 31
22 1
10 16
20 29
35 18
18 25
7 36
24 26
2 32
13 8
17 39
2 19
13 36
4 30
24 10
22 36
16 11
18 33
34 6
27 20
5 20
15 12
8 2
28 3
35 31
15 24
29 21
21 30
26 38
37 27
0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1

output:

result:

ok single line: '19'

Test #10:

score: 0

Accepted

time: 1ms

memory: 9856kb

input:

40
5 16
2 4
30 27
15 39
8 3
14 16
3 23
34 2
35 27
26 40
12 30
36 21
25 26
10 7
5 3
7 15
14 17
29 33
13 40
21 1
12 19
38 22
29 9
37 32
7 17
13 33
3 28
19 40
11 26
37 34
40 6
20 6
6 18
25 38
24 21
18 34
17 21
35 24
31 36
1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1

output:

result:

ok single line: '21'

Test #11:

score: 0

Accepted

time: 4ms

memory: 9840kb

input:

40
17 25
12 22
4 30
36 31
21 19
15 25
4 19
40 1
16 20
23 37
20 12
26 1
31 17
18 27
35 5
13 33
4 29
25 11
31 32
17 16
9 22
34 5
34 27
11 8
38 4
17 40
24 11
25 14
10 22
6 18
8 37
30 39
2 25
29 22
26 35
2 7
38 13
3 15
38 28
0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0

Accepted

time: 4ms

memory: 9928kb

input:

40
39 23
23 16
23 24
23 5
17 23
23 32
6 23
23 8
23 10
9 23
13 23
25 23
23 34
12 23
36 23
40 23
23 18
23 2
23 28
33 23
23 1
3 23
23 38
23 22
23 7
31 23
23 37
11 23
35 23
20 23
23 15
23 21
30 23
23 29
23 26
23 27
23 14
23 4
19 23
1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 ...

output:

result:

ok single line: '14'

Test #13:

score: 0

Accepted

time: 5ms

memory: 9876kb

input:

39
5 17
5 32
20 5
5 11
24 5
5 18
15 5
5 37
25 5
29 5
14 5
5 34
6 5
16 5
10 5
5 9
5 1
5 23
4 5
5 12
26 5
5 39
27 5
19 5
5 36
5 2
5 38
21 5
5 33
28 5
5 31
5 7
5 8
22 5
13 5
5 3
5 35
5 30
0 0 1 0 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0

output:

result:

ok single line: '13'

Subtask #4:

score: 10

Accepted

Test #14:

score: 10

Accepted

time: 25ms

memory: 21924kb

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:

result:

ok single line: '49772'

Test #15:

score: 0

Accepted

time: 27ms

memory: 21716kb

input:

98273
46112 46113
46912 46913
74330 74329
44926 44925
45873 45874
67146 67145
5397 5396
2561 2560
82735 82736
94041 94040
26762 26761
24535 24534
29483 29482
36116 36115
6390 6391
84795 84796
21112 21113
78994 78993
48299 48298
174 173
15717 15716
93544 93545
32500 32499
177 176
639 638
46383 46384
...

output:

impossible

result:

ok single line: 'impossible'

Test #16:

score: 0

Accepted

time: 27ms

memory: 21988kb

input:

100000
26307 26308
590 591
98899 98900
50854 50855
77753 77754
38014 38013
75156 75157
10027 10028
83934 83935
43862 43863
65101 65102
7784 7783
93163 93164
29841 29840
3862 3863
6542 6541
6432 6433
93756 93757
68690 68691
51050 51049
18593 18592
15431 15430
82511 82512
45462 45461
64205 64204
94833...

output:

result:

ok single line: '49874'

Subtask #5:

score: 0

Wrong Answer

Test #17:

score: 0

Wrong Answer

time: 22ms

memory: 16444kb

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:

-1804644422573055474

result:

wrong answer 1st lines differ - expected: 'impossible', found: '-1804644422573055474'

Subtask #6:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted