QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#812595	#9806. Growing Tree	fzx	WA	1ms	3924kb	C++14	2.1kb	2024-12-13 16:52:41	2024-12-13 16:52:45

Judging History

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

[2024-12-13 16:52:45]
评测

测评结果：WA
用时：1ms
内存：3924kb

查看

[2024-12-13 16:52:41]
提交

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]]) 
        if (s[id3[R]].find(w+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+dd[x][1]-dd[x][0]);
        DFS(x-1,t);
        lazy1[id3[x]]-=dd[x][0];
        for (int w:s[id3[R]])
            s[id3[x]].erase(s[id3[x]].find(w+dd[x][1]-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;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3732kb

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: -100

Wrong Answer

time: 0ms

memory: 3924kb

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:

result:

wrong answer 4th numbers differ - expected: '2', found: '1'