QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#222550#7607. The Doubling Game 2ucup-team135#WA 12ms37732kbC++204.9kb2023-10-21 17:35:172023-10-21 17:35:19

Judging History

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

  • [2023-10-21 17:35:19]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:37732kb
  • [2023-10-21 17:35:17]
  • 提交

answer

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#define debug(x) do { cerr << #x << ": " << x << endl; } while(0)
#define debug2(x, y) do { cerr << #x << ": " << x << ". " << #y << ": " << y << endl; } while(0)
#define debug3(x, y, z) do { cerr << #x << ": " << x << ". " << #y << ": " << y << ". " << #z << ": " << z << endl; } while(0)
#define debug_all(x) do { cerr << #x << ": "; for (const auto &v : x) cerr << v << ' '; cerr << endl; } while(0)
#else
#define debug(x)
  #define debug2(x, y)
  #define debug3(x, y, z)
  #define debug_all(x)
#endif
#include <bits/stdc++.h>

#define int long long

using namespace std;
using ll = long long;
using ld = long double;
void solve();
int32_t main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int t = 1;
    for (int tc = 0; tc < t; ++tc) {
        solve();
    }
    return 0;
}
const int maxn=1e6+5;
vector<int> a[maxn];
int32_t dp[300005][20][2];
int h[1<<20];
bool used[maxn];
const int p=1e9+7;
int is2[maxn];
void dfs(int x)
{
    used[x]=true;
    vector<int> ch;
    for(int v:a[x]) {
        if (!used[v]) {
            dfs(v);
            ch.push_back(v);
        }
    }
    for(int i=1;i<20;++i) {
        int i1=i;
        set<int> g = {0};
        h[0] = 1;
        for (int v: ch) {
            vector<int> ins;
            set<int>::iterator it = (g.end());
            while (true) {
                --it;
                int j = (*it);
                for (int i = 19; i >= 0; --i) {
                    if(i>=i1) continue;
                    if (i != 0 && dp[v][i][0] && (j & (1 << (i - 1))) == 0) {
                        h[j + (1 << (i - 1))] += h[j]*dp[v][i][0];
                        h[j + (1 << (i - 1))] %= p;
                        ins.push_back(j + (1 << (i - 1)));
                    } else if (i == 0) {
                        h[j] *= dp[v][i][0];
                        h[j] %= p;
                    }
                }
                if (it == g.begin()) break;
            }
            for (int x: ins) g.insert(x);
        }
        dp[x][i][0]=h[(1<<(i-1))-1];dp[x][i][0]%=p;
        for(int mask:g) h[mask]=0;
    }
    for(int i=1;i<20;++i)
    {
        int i1=i;
        set<int> g = {0};
        h[0] = 1;
        for (int v: ch) {
            vector<int> ins;
            set<int>::iterator it = (g.end());
            while (true) {
                --it;
                int j = (*it);
                for (int i = 19; i >= 0; --i) {
                    if(i>i1) continue;
                    int dp1=dp[v][i][0];
                    if(i==i1) {dp1+=dp[v][i][1];dp1%=p;}
                    if (i != 0 && dp1 && (j & (1 << (i - 1))) == 0) {
                        h[j + (1 << (i - 1))] += h[j]*dp1;
                        h[j + (1 << (i - 1))] %= p;
                        ins.push_back(j + (1 << (i - 1)));
                    } else if (i == 0) {
                        h[j] *= dp[v][i][0];
                        h[j] %= p;
                    }
                }
                if (it == g.begin()) break;
            }
            for (int x: ins) g.insert(x);
        }
        //if(x==3) cout<<i<<" i "<<h[(1<<i)-1]<<" h "<<endl;
        if(i==1) {dp[x][0][0]+=h[0];dp[x][0][0]%=p;}
        dp[x][0][0]+=2*h[(1<<i)-1];dp[x][0][0]%=p;
        for(int mask:g) h[mask]=0;
    }
    for(int i1=1;i1<20;++i1)
    {
        for(int j1=i1+1;j1<20;++j1)
        {
            set<int> g = {0};
            h[0] = 1;
            for (int v: ch) {
                vector<int> ins;
                set<int>::iterator it = (g.end());
                while (true) {
                    --it;
                    int j = (*it);
                    for (int i = 19; i >= 0; --i) {
                        if(i>j1) continue;
                        int dp1=dp[v][i][0];
                        if(i==j1) {dp1+=dp[v][i][1];dp1%=p;}
                        if (i != 0 && dp1 && (j & (1 << (i - 1))) == 0) {
                            h[j + (1 << (i - 1))] += h[j]*dp1;
                            h[j + (1 << (i - 1))] %= p;
                            ins.push_back(j + (1 << (i - 1)));
                        } else if (i == 0) {
                            h[j] *= dp[v][i][0];
                            h[j] %= p;
                        }
                    }
                    if (it == g.begin()) break;
                }
                for (int x: ins) g.insert(x);
            }
            dp[x][i1][1]+=h[(1<<j1)-(1<<(i1-1))-1];dp[x][i1][1]%=p;
            for(int mask:g) h[mask]=0;
        }
    }
    //cout<<x<<" x "<<endl;
    //for(int i=0;i<=5;++i) cout<<dp[x][i][0]<<' '<<dp[x][i][1]<<endl;
    //cout<<endl;
}
void solve() {
    for(int i=1;i<1000000;i*=2) is2[i]=1;
    int n;cin>>n;
    for(int i=0;i<n-1;++i) {int x,y;cin>>x>>y;--x;--y;a[x].push_back(y);a[y].push_back(x);}
    dfs(0);
    cout<<(dp[0][0][0]%p+p)%p;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 37732kb

input:

5
1 2
1 3
1 4
4 5

output:

21

result:

ok single line: '21'

Test #2:

score: 0
Accepted
time: 3ms
memory: 36040kb

input:

1

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Wrong Answer
time: 12ms
memory: 37684kb

input:

128
11 32
116 81
65 4
117 47
5 81
104 30
61 8
82 59
95 20
92 29
29 127
97 39
123 33
59 128
115 33
83 67
74 16
77 33
64 73
124 123
8 127
61 51
101 122
35 90
119 116
112 27
81 93
109 123
54 1
119 100
116 16
65 47
67 27
22 105
76 87
36 39
27 96
72 31
91 123
21 105
118 12
110 48
121 72
14 115
24 16
106 ...

output:

389992204

result:

wrong answer 1st lines differ - expected: '508800953', found: '389992204'