QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#812602#9806. Growing TreefzxRE 1ms3872kbC++142.2kb2024-12-13 17:00:572024-12-13 17:00:58

Judging History

This is the latest submission verdict.

  • [2024-12-13 17:00:58]
  • Judged
  • Verdict: RE
  • Time: 1ms
  • Memory: 3872kb
  • [2024-12-13 17:00:57]
  • Submitted

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...

output:


result: