QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #812602 | #9806. Growing Tree | fzx | RE | 1ms | 3872kb | C++14 | 2.2kb | 2024-12-13 17:00:57 | 2024-12-13 17:00:58 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int INF=2e3+5;
int n,ff[INF],res,id3[INF],lazy1[INF],dd[INF][3];
vector < pii > e[INF];
multiset <int> s[INF];
void DFS(int x,int t) {
if (x==(1ll<<(t-1))-1) t--;
if (!x) {
res=min(res,ff[1]);
return ;
}
int L=x*2,R=x*2+1,fl=0;
for (int w:s[id3[L]]) {
// cerr<<w+dd[x][0]-dd[x][1]<<" "<<x<<" awejirqowiejr\n";
if (s[id3[R]].find(w+lazy1[id3[L]]-lazy1[id3[R]]+dd[x][0]-dd[x][1])!=s[id3[R]].end())
{fl=1;break;}
}
// cerr<<id3[L]<<" "<<id3[R]<<" "<<(s[7].find(0)!=s[7].end())<<" qweirjqworejqwre\n";
// cerr<<fl<<" "<<dd[x][0]<<" "<<dd[x][1]<<" "<<x<<" qwerojiqw\n";
if (fl) {
int F=0;
for (int u=1;u<=t;u++) {
// cerr<<u<<" "<<t<<" qwerijqwr\n";
ff[u]++;
if (ff[u]>n-u+1) F=1;
}
if (F) {
for (int u=1;u<=t;u++)
ff[u]--;
return ;
}
id3[x]=id3[R];lazy1[id3[x]]+=dd[x][1];
DFS(x-1,t);
lazy1[id3[x]]-=dd[x][1];
id3[x]=id3[L];lazy1[id3[x]]+=dd[x][0];
DFS(x-1,t);
lazy1[id3[x]]-=dd[x][0];
for (int u=1;u<=t;u++) {
ff[u]--;
}
} else {
id3[x]=id3[L];lazy1[id3[x]]+=dd[x][0];
for (int w:s[id3[R]])
s[id3[x]].insert(w+lazy1[id3[R]]+dd[x][1]-lazy1[id3[L]]);
DFS(x-1,t);
for (int w:s[id3[R]])
s[id3[x]].erase(s[id3[x]].find(w+lazy1[id3[R]]+dd[x][1]-lazy1[id3[L]]));
lazy1[id3[x]]-=dd[x][0];
}
}
void solve() {
cin>>n;int N=((1ll<<(n+1))-1);res=1e9;
for (int i=0;i<=N+3;i++)
e[i].clear(),s[i].clear(),lazy1[i]=0;
for (int w=0;w<=n+3;w++) ff[w]=0;
for (int i=2;i<=N;i++) {
int x=0;cin>>x;
dd[i/2][i&1]=x;
}
for (int i=(1ll<<n);i<=N;i++)
s[i].insert(0),id3[i]=i;
DFS((1ll<<n)-1,n+1);
if (res>n*2) cout<<"-1\n";
else cout<<res<<"\n";
}
signed main()
{
ios::sync_with_stdio(false);
int t=0;cin>>t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
input:
3 2 1 2 4 3 2 1 2 1 2 3 3 2 1 2 1 2 3 3 1 1
output:
1 2 -1
result:
ok 3 number(s): "1 2 -1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
94 5 44 65 38 61 64 94 71 53 65 10 24 36 98 74 11 4 5 46 72 34 9 24 37 32 76 29 48 88 17 14 36 4 22 6 71 53 24 61 89 79 39 57 99 61 27 85 99 46 81 75 90 25 16 13 1 87 55 81 56 78 67 2 3 83 3 74 14 45 17 22 41 62 74 25 1 56 22 7 21 73 83 99 3 91 16 53 8 10 49 29 54 81 45 10 12 68 32 9 30 11 99 85 73 ...
output:
2 0 -1 2 0 1 -1 0 0 3 0 0 0 1 2 1 0 2 0 1 0 -1 0 -1 0 0 -1 -1 -1 -1 -1 4 -1 0 3 2 7 -1 -1 -1 1 2 4 0 0 2 7 1 6 0 -1 2 -1 0 0 0 -1 1 -1 -1 0 0 1 1 -1 0 1 2 0 -1 0 0 1 1 -1 0 -1 0 0 0 -1 3 -1 1 7 0 0 0 0 1 0 -1 3 3
result:
ok 94 numbers
Test #3:
score: -100
Runtime Error
input:
1 10 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 10000...