Submission #923912

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
923912	2024-02-08T06:14:08 Z	Pring	Deblo (COCI18_deblo)	C++17	90 / 90	117 ms	15648 KB

deblo

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 100005, LGC = 22;
int n, a[MXN];
vector<int> edge[MXN];
int sum;
bitset<MXN> die;
int c[2][LGC], d[2][LGC];
int sz[MXN];

void GET_SZ(int id, int par) {
    sz[id] = 1;
    for (auto &i : edge[id]) {
        if (i == par) continue;
        if (die[i]) continue;
        GET_SZ(i, id);
        sz[id] += sz[i];
    }
}

int GET_CD(int id, int par, int N) {
    for (auto &i : edge[id]) {
        if (i == par) continue;
        if (die[i]) continue;
        if (sz[i] > N / 2) return GET_CD(i, id, N);
    }
    return id;
}

void DFS(int id, int par, int cd, int now) {
    now ^= a[id];
    sum += (now ^ a[cd]);
    debug(id, now);
    FOR(j, 0, LGC) d[((now & (1 << j)) ? 1 : 0)][j]++;
    for (auto &i : edge[id]) {
        if (i == par) continue;
        if (die[i]) continue;
        DFS(i, id, cd, now);
    }
}

void DO(int cd) {
    debug(cd);
    FOR(i, 0, 2) FOR(j, 0, LGC) {
        c[i][j] = 0;
        d[i][j] = 0;
    }
    for (auto &i : edge[cd]) {
        if (die[i]) continue;
        debug(i);
        DFS(i, cd, cd, 0);
        // FOR(j, 0, LGC) cout << d[0][j] << ' ';
        // cout << '\n';
        // FOR(j, 0, LGC) cout << d[1][j] << ' ';
        // cout << '\n';
        FOR(j, 0, LGC) {
            int h = ((a[cd] & (1 << j)) ? 1 : 0);
            sum += ((c[0][j] * d[1 ^ h][j]) << j);
            sum += ((c[1][j] * d[h][j]) << j);
            c[0][j] += d[0][j];
            c[1][j] += d[1][j];
            d[0][j] = 0;
            d[1][j] = 0;
        }
    }
}

void DC(int id) {
    GET_SZ(id, 0);
    if (sz[id] == 1) return;
    int cd = GET_CD(id, 0, sz[id]);
    DO(cd);
    die[cd] = true;
    for (auto &i : edge[cd]) {
        if (die[i]) continue;
        DC(i);
    }
}

void miku() {
    int x, y;
    cin >> n;
    FOR(i, 1, n + 1) {
        cin >> a[i];
        sum += a[i];
    }
    FOR(i, 1, n) {
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    DC(1);
    cout << sum << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

Compilation message

deblo.cpp: In function 'void DFS(long long int, long long int, long long int, long long int)':
deblo.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
deblo.cpp:50:5: note: in expansion of macro 'debug'
   50 |     debug(id, now);
      |     ^~~~~
deblo.cpp: In function 'void DO(long long int)':
deblo.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
deblo.cpp:60:5: note: in expansion of macro 'debug'
   60 |     debug(cd);
      |     ^~~~~
deblo.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
deblo.cpp:67:9: note: in expansion of macro 'debug'
   67 |         debug(i);
      |         ^~~~~

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3420 KB	Output is correct
2	Correct	1 ms	3420 KB	Output is correct
3	Correct	1 ms	3420 KB	Output is correct
4	Correct	2 ms	3420 KB	Output is correct
5	Correct	2 ms	3420 KB	Output is correct
6	Correct	105 ms	15648 KB	Output is correct
7	Correct	100 ms	15576 KB	Output is correct
8	Correct	115 ms	10976 KB	Output is correct
9	Correct	117 ms	10444 KB	Output is correct
10	Correct	105 ms	9820 KB	Output is correct