QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#864959	#2562. Fake Plastic Trees 2	ran_qwq	WA	5ms	6656kb	C++14	3.2kb	2025-01-21 12:09:47	2025-01-21 12:09:47

Judging History

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

[2025-01-21 12:09:47]
评测

测评结果：WA
用时：5ms
内存：6656kb

查看

[2025-01-21 12:09:47]
提交

answer

#include<bits/stdc++.h>
#define il inline
#define ui unsigned int
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define ldb long double
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define fir first
#define sec second
#define gc getchar
#define pc putchar
#define mst(a,x) memset(a,x,sizeof a)
#define mcp(a,b) memcpy(a,b,sizeof b)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pct __builtin_popcount
using namespace std;
const int N=1010,M=55,INF=0x3f3f3f3f,MOD=998244353;
const ll INFll=0x3f3f3f3f3f3f3f3f;
il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il void wr(int x) {if(x==INT_MIN) return printf("-2147483648"),void(); if(x<0) return pc('-'),wr(-x); if(x<10) return pc(x+'0'),void(); wr(x/10),pc(x%10+'0');}
il void wrll(ll x) {if(x==LLONG_MIN) return printf("-9223372036854775808"),void(); if(x<0) return pc('-'),wrll(-x); if(x<10) return pc(x+'0'),void(); wrll(x/10),pc(x%10+'0');}
il void wr(int x,char *s) {wr(x),printf("%s",s);}
il void wrll(ll x,char *s) {wrll(x),printf("%s",s);}
il int vmod(int x) {return x>=MOD?x-MOD:x;}
il int vadd(int x,int y) {return vmod(x+y);}
il int vsub(int x,int y) {return vmod(x-y+MOD);}
il int vmul(int x,int y) {return 1ll*x*y%MOD;}
il int qpow(int x,int y) {int r=1; for(;y;y>>=1,x=vmul(x,x)) if(y&1) r=vmul(r,x); return r;}
il void cadd(int &x,int y) {x=vmod(x+y);}
il void csub(int &x,int y) {x=vmod(x-y+MOD);}
il void cmul(int &x,int y) {x=vmul(x,y);}
il void cmax(int &x,int y) {x<y&&(x=y);}
il void cmaxll(ll &x,ll y) {x<y&&(x=y);}
il void cmin(int &x,int y) {x>y&&(x=y);}
il void cminll(ll &x,ll y) {x>y&&(x=y);}
int n,m,id,hd[N],b[N][M]; ll l,r,a[N]; vector<ll> g[M],f[N][M];
struct EDGE {int to,ne;} e[N*2];
il void add(int u,int v) {e[++id]={v,hd[u]},hd[u]=id;}
void dfs(int u,int fa) {
	f[u][0].pb(a[u]);
	for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)!=fa) {
		dfs(v,u);
		for(int j=0;j<=m;j++) g[j].clear();
		for(int j=0;j<=m;j++) for(int k=0;k<=m-j;k++) {
			for(ll x:f[u][j]) for(ll y:f[v][k]) if(x+y<=r) g[j+k].pb(x+y);
			if(j+k<m&&b[v][k]) for(ll x:f[u][j]) g[j+k+1].pb(x);
		}
		for(int j=0;j<=m;j++) {
			sort(g[j].begin(),g[j].end()),f[u][j].clear();
			for(ll x:g[j]) if(x<=r) {
				if(f[u][j].size()&&x==f[u][j].back()) continue;
				while(f[u][j].size()>1&&x-*prev(f[u][j].rbegin())<=r-l) f[u][j].pop_back();
				f[u][j].pb(x);
			}
		}
	}
	for(int i=0;i<=m;i++) b[u][i]=f[u][i].size()&&f[u][i].back()>=l;
}
void QwQ() {
	n=rd(),m=rd(),l=rdll(),r=rdll(),id=0,mst(hd,0),mst(b,0);
	for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) f[i][j].clear();
	for(int i=1;i<=n;i++) a[i]=rdll();
	for(int i=1,u,v;i<n;i++) u=rd(),v=rd(),add(u,v),add(v,u);
	dfs(1,0);
	for(int i=0;i<=m;i++) wr(b[1][i]); puts("");
}
signed main() {
//	freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	int T=rd(); while(T--) QwQ();
}
/*
3
4 3 1 2
1 1 1 1
1 2
2 3
3 4
4 3 1 2
1 1 1 1
1 2
1 3
1 4
4 3 0 0
1 1 1 1
1 2
1 3
1 4
*/

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 5120kb

input:

output:

0111
0011
0000

result:

ok 3 tokens

Test #2:

score: 0

Accepted

time: 1ms

memory: 5120kb

input:

100
10 9 18 50
18 0 9 8 11 11 13 16 9 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 38 50
4 10 11 13 19 6 14 14 20 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 26 50
6 1 12 7 1 12 20 2 0 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 29 50
16 13 1 17 20 15 0 3 6 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10...

output:

result:

ok 100 tokens

Test #3:

score: 0

Accepted

time: 1ms

memory: 5120kb

input:

100
10 9 23 50
13 10 9 11 14 13 11 9 14 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 11 50
11 9 9 9 14 7 9 12 14 5
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 27 50
14 13 9 13 9 13 9 14 14 5
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 41 50
8 10 10 13 8 6 12 7 10 5
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1...

output:

result:

ok 100 tokens

Test #4:

score: 0

Accepted

time: 1ms

memory: 5120kb

input:

100
10 9 17 50
9 8 10 12 12 10 12 10 9 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 19 50
10 9 8 10 12 12 8 11 12 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 46 50
8 8 10 10 10 8 9 10 11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 9 50
9 8 11 10 11 10 10 11 11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 ...

output:

result:

ok 100 tokens

Test #5:

score: 0

Accepted

time: 0ms

memory: 5120kb

input:

100
10 9 10 50
10 11 11 10 9 9 11 9 11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 47 50
9 9 9 11 9 10 10 10 10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 49 50
9 10 9 11 11 9 11 10 10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 19 50
10 9 11 11 10 11 11 9 9 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10...

output:

result:

ok 100 tokens

Test #6:

score: 0

Accepted

time: 2ms

memory: 5120kb

input:

100
10 9 50 50
50 50 50 50 50 50 50 50 50 50
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 50 50
50 50 50 50 50 50 50 50 50 50
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 50 50
50 50 50 50 50 50 50 50 50 50
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 50 50
50 50 50 50 50 50 50 50 50 50
1 2
2 3
3 4
4 5
5 6
6...

output:

result:

ok 100 tokens

Test #7:

score: 0

Accepted

time: 1ms

memory: 5120kb

input:

100
10 9 1793281831312430 2579712950976669
883262428445148 926941407766037 874610589009581 918671242302849 917202064660727 848094660280817 810513162735522 862049976415823 844577745576407 873085228984439
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 1890762965379103 2701769025604615
804306683243252 81402...

output:

result:

ok 100 tokens

Test #8:

score: 0

Accepted

time: 1ms

memory: 5120kb

input:

100
10 9 930392660078775 2806634959843587
930392660078775 905044994636391 985788965763349 912985101122684 987674992837788 921047708030944 933871032635272 924074917003015 906465081663363 976094961177209
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 1883664986961563 2834193280785472
958998107162380 924666...

output:

result:

ok 100 tokens

Test #9:

score: 0

Accepted

time: 1ms

memory: 5120kb

input:

100
10 9 999994984493978 2999942395429624
999994984493978 999939388770002 999967949978069 999931885129608 999990661850258 999984525481315 999963292059809 999975054238715 999981969673638 999985371517271
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 999995366940426 2999765738847089
999995366940426 9999556...

output:

result:

ok 100 tokens

Test #10:

score: 0

Accepted

time: 2ms

memory: 5120kb

input:

100
10 9 999999979118283 2999999819537067
999999979118283 999999975440440 999999958461371 999999979080922 999999991176682 999999985652594 999999984182267 999999928654853 999999990678448 999999900203766
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 999999951922360 2999999720940184
999999951922360 9999999...

output:

result:

ok 100 tokens

Test #11:

score: 0

Accepted

time: 2ms

memory: 5120kb

input:

100
10 9 999999999999480 2999999999998668
999999999999480 999999999999623 999999999999311 999999999999062 999999999999032 999999999999420 999999999999039 999999999999706 999999999999079 999999999999883
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 999999999999062 2999999999997761
999999999999062 9999999...

output:

result:

ok 100 tokens

Test #12:

score: 0

Accepted

time: 0ms

memory: 5120kb

input:

100
10 9 809217843509205176 1000000000000000000
819047520089857618 993247146028854493 979024090970900146 946916558454439857 809217843509205176 908857838415646655 809854521131167579 931917514552091282 890253286257158425 872828244740194237
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 810517126615250421 1...

output:

result:

ok 100 tokens

Test #13:

score: 0

Accepted

time: 1ms

memory: 5120kb

input:

100
10 9 990469099227929497 1000000000000000000
997087653799379867 998602320157374700 997500855340614575 998172426490578932 998173419961973183 997315871904813866 990469099227929497 991331794758268536 996329227071528815 994942302495919962
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 990138767121283623 1...

output:

result:

ok 100 tokens

Test #14:

score: 0

Accepted

time: 2ms

memory: 5120kb

input:

100
10 9 1000000000000000000 1000000000000000000
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 9 100000000...

output:

result:

ok 100 tokens

Test #15:

score: 0

Accepted

time: 5ms

memory: 6656kb

input:

1
1000 50 3 50
0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1...

output:

000000000011111111111111111111111111111111111111111

result:

ok "000000000011111111111111111111111111111111111111111"

Test #16:

score: 0

Accepted

time: 5ms

memory: 6144kb

input:

1
1000 50 16 50
0 2 1 2 0 0 0 1 0 2 1 0 2 2 1 2 2 2 1 0 0 1 1 0 2 1 2 1 2 1 0 0 1 1 0 2 2 2 2 0 0 2 2 2 1 1 0 1 1 1 1 1 0 2 1 1 2 2 2 0 0 2 0 0 1 1 0 0 2 1 2 1 1 1 2 0 0 2 2 2 1 1 1 0 1 0 1 1 2 2 0 0 2 0 1 2 2 0 0 0 2 2 1 2 1 0 2 1 1 0 1 0 0 1 1 0 0 1 0 0 2 2 2 0 0 1 2 2 1 1 2 2 0 2 2 0 1 0 1 0 1 1 ...

output:

000000000000000000001111111111111111111111111111111

result:

ok "000000000000000000001111111111111111111111111111111"

Test #17:

score: 0

Accepted

time: 3ms

memory: 6272kb

input:

1
1000 50 12 50
3 0 3 3 0 1 1 0 0 1 3 2 2 0 0 1 2 1 0 2 2 1 3 2 0 3 3 1 1 3 2 3 3 2 2 2 1 3 2 3 2 1 0 0 2 3 2 0 1 2 3 3 1 3 1 2 0 3 1 1 3 0 0 0 1 3 2 1 2 0 1 0 1 0 2 2 3 0 1 3 1 3 0 0 1 0 0 1 1 1 0 0 3 1 0 0 0 3 3 3 1 1 1 1 1 2 2 3 1 1 1 1 2 3 2 3 3 0 1 0 0 3 0 2 0 2 1 0 0 3 1 1 2 1 2 1 3 0 3 3 1 0 ...

output:

000000000000000000000000000000111111111111111111111

result:

ok "000000000000000000000000000000111111111111111111111"

Test #18:

score: -100

Wrong Answer

time: 2ms

memory: 5504kb

input:

1
1000 50 42 50
1 1 2 0 2 2 2 3 1 4 1 2 2 2 3 4 3 2 3 0 2 1 4 4 2 1 1 3 3 4 3 2 1 1 0 3 2 1 4 3 4 0 0 3 3 2 1 0 1 0 0 4 1 3 3 1 4 0 0 1 4 1 3 2 4 2 4 4 3 4 0 1 0 1 1 1 0 4 3 3 1 2 4 3 4 3 1 2 1 4 3 0 3 4 1 4 4 0 0 2 1 1 4 3 3 2 4 4 1 1 3 3 1 1 4 3 2 3 0 2 4 4 4 1 0 3 2 1 0 3 4 4 3 4 0 2 2 0 1 1 4 2 ...

output:

000000000000000000000000000000000000000000111011000

result:

wrong answer 1st words differ - expected: '000000000000000000000000000000000000000000111111000', found: '000000000000000000000000000000000000000000111011000'