QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#595944 | #5252. Deforestation | QHhee004# | WA | 12ms | 6944kb | C++17 | 1.2kb | 2024-09-28 14:49:13 | 2024-09-28 14:49:18 |
Judging History
answer
#include<iostream>
#include<algorithm>
using namespace std;
int W,c;
const int N=1e5+5;
struct Tree {
int w,d;
} t[N];
int wight[N],branch[N];
int tot,hd[N],nxt[N<<1],to[N<<1];
void addedge(int u,int v) {
++tot,to[tot]=v,nxt[tot]=hd[u],hd[u]=tot;
}
void input(int x,int d) {
int g=0;
while(g<d) {
++g,++c;
scanf("%d%d",&t[c].w,&t[c].d);
addedge(x,c);
input(c,t[c].d);
}
}
int dfs(int x) {
int sum=0,top=0;
for(int i=hd[x]; i; i=nxt[i]) {
int goal=to[i];
sum+=dfs(goal);
}
for(int i=hd[x]; i; i=nxt[i])
if(t[to[i]].w)wight[++top]=t[to[i]].w;
sort(wight+1,wight+1+top);
int L=1,R=top,g=0;
while(L<=R) {
branch[++g]=wight[R--];
while(L<=R&&branch[g]+wight[L]<=W)branch[g]+=wight[L],L++;
}
if(g) {
int mn=1e9;
for(int i=1; i<=g; i++)
mn=min(mn,branch[i]);
if(mn==W)sum+=g;
else if(mn+t[x].w>W) t[x].w=mn+t[x].w-W,sum+=g;
else t[x].w+=mn,sum+=g-1;
sum=sum+t[x].w/W;
t[x].w%=W;
} else {
sum=sum+t[x].w/W;
t[x].w%=W;
}
return sum;
}
int main() {
scanf("%d",&W);
++c;
scanf("%d%d",&t[c].w,&t[c].d);
input(1,t[1].d);
printf("%d\n",dfs(1)+(t[1].w!=0));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 6944kb
input:
999900000 7339 3 14947 2 12850 3 8986 10 11599 9 8889 10 10711 4 8015 1 11626 0 9492 1 7017 0 8863 0 8632 0 5321 5 9906 0 11687 0 9845 0 10469 0 11708 0 14950 5 11934 0 11922 0 13101 0 12000 0 9082 0 9273 5 12296 0 6119 0 9201 0 12652 0 12957 0 7454 5 12515 0 12976 0 10358 0 13997 0 8371 0 10181 5 8...
output:
1
result:
ok single line: '1'
Test #2:
score: -100
Wrong Answer
time: 9ms
memory: 6064kb
input:
2 1 99999 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 ...
output:
50000
result:
wrong answer 1st lines differ - expected: '99999', found: '50000'