QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245595#7558. Abstractlukap_ML 1ms4508kbC++142.4kb2023-11-10 04:05:222023-11-10 04:05:22

Judging History

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

  • [2023-11-10 04:05:22]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:4508kb
  • [2023-11-10 04:05:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 998244353;
const ll baza = (1 << 32);

int add (int a, int b) {
    return (ll) ((ll) a + b + MOD) % MOD;
}

int mull (int a, int b) {
    return (ll) ((ll) a * b) % MOD;
}

struct big_num {
    vector<ll> zn;

    void ocisti () {
        ll vis = 0;
        for (ll &x: zn) {
            x += vis;
            vis = x >> baza;
            x &= (1LL << baza) - 1;
        }
        if (vis) zn.push_back (vis);
    }

    void mul (ll y) {
        for (ll &x: zn) x *= y;
        ocisti ();
    }

    void operator += (const big_num & rhs) {
        while (zn.size () < rhs.zn.size ()) zn.push_back (0);

        for (int i = 0; i < rhs.zn.size (); i++) {
            zn[i] += rhs.zn[i];
        }
        ocisti();
    }

    void jedan () {
        ocisti ();
        zn.push_back (1);
    }

    int log () {
//        cout << zn.back () << ' ' << log2(zn.back()) << "\n";
        int sum = 0;
        for (int i = 0; i < zn.size () - 1; i++) sum = add (sum, mull (zn[i], 32));
        sum = add (sum, ceil(log2(zn.back () + 1)));
        return sum;
    }
};

const int MAXN = 1e4 + 500;
const int MAXM = 1e5 + 500;

int n, m, val[MAXN];
vector<int> children[MAXN], parents[MAXN];
int sink;
big_num dp[MAXN];
int bio[MAXN];
big_num uk;
vector<int> v;

void topsort (int x) {
    bio[x] = 1;
    for (auto it: children[x]) {
        if (bio[it] == 0) {
            topsort (it);
        }
    }
    v.push_back(x);
}

int main () {
    ios_base::sync_with_stdio (false);
    cin.tie (0);

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> val[i];

    for (int i = 0; i < m; i++) {
        int a,b;
        cin >> a >> b;
        a--;b--;

        children[a].push_back (b);
        parents[b].push_back (a);
    }

    for (int i = 0; i < n; i++) {
        if (children[i].size () == 0) sink = i;
    }

    for (int i = 0; i < n; i++) {
        if (bio[i] == 0) topsort (i);
    }

    dp[sink].jedan ();
    for (auto x: v) {
        if (x != sink) dp[x].mul(2);
        for (auto it: parents[x]) dp[it] += dp[x];
    }

//    for (int i = 0; i < n; i++) cout << dp[i].visak() << ' ';
//    cout << "\n";

    for (int i = 0; i < n; i++) dp[i].mul (val[i]);
    for (int i = 0; i < n; i++) uk += dp[i];

    cout << uk.log();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4504kb

input:

3 2
1 1 1
1 2
2 3

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4428kb

input:

6 8
1 1 4 5 1 4
1 4
1 5
2 3
2 5
3 4
4 5
4 6
5 6

output:

8

result:

ok 1 number(s): "8"

Test #3:

score: 0
Accepted
time: 1ms
memory: 4508kb

input:

5 6
7 2 3 6 6
1 2
1 4
2 3
3 4
3 5
4 5

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: -100
Memory Limit Exceeded

input:

7286 80481
637288250 628935175 588324396 766398783 663989874 865498593 695497968 630237220 19939888 448367842 412696777 111291257 304805809 585852799 58270069 391993802 606944382 827515045 389862501 643981354 160381074 324288921 257053597 980043955 417281046 870855665 360154617 60327683 966755927 55...

output:

-150994942

result: