oj.uz

답안 #1003039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003039 2024-06-20T03:41:41 Z PurpleCrayon Spy 3 (JOI24_spy3) C++17
99 / 100
 313 ms 143020 KB 
#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;

namespace {

const ll INF = 1e18+10;
const int N = 2e4+10, Q = 16;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

vector<int> tree[N];
int mine[N];

int dfs_sub(int c) {
    int ans = 0;
    if (mine[c] != -1) ans |= 1 << mine[c];
    for (int nxt : tree[c]) ans |= dfs_sub(nxt);
    return ans;
}

string enc(ll x, int len) {
    string ans;
    for (int i = 0; i < len; i++) {
        ans += char('0' + x % 2);
        x /= 2;
    }
    return ans;
}

string build_tree(int mask, map<int, int>& peel) {
    if (__builtin_popcount(mask) == 1) return "";
    return build_tree(peel[mask], peel) + "0" + build_tree(mask ^ peel[mask], peel) + "1";
}

ll memo_tot[1 << Q];
ll fact[Q + 1];
ll nck(ll a, ll b) {
    return fact[a] / fact[b] / fact[a - b];
}

ll cnt_tot(int mask, map<int, int>& peel) {
    if (memo_tot[mask] != -1) return memo_tot[mask];
    if (__builtin_popcount(mask) == 1) return 1;

    assert(peel.count(mask));
    int part = peel[mask];
    return cnt_tot(part, peel) * cnt_tot(mask ^ part, peel) * nck(__builtin_popcount(mask) - 1, __builtin_popcount(part) - 1);
}

ll memo_less[1 << Q][Q][Q];
ll cnt_less(int l, int r, int mask, const vector<int>& p, map<int, int>& peel) { // number of things less than it
    assert(__builtin_popcount(mask) == r - l + 1);
    if (memo_less[mask][l][r] != -1) return memo_less[mask][l][r];
    if (l == r) {
        return __builtin_ctz(mask) < p[l];
    }

    int who_peel = 0;
    for (int i = l; i <= r; i++) who_peel |= 1 << p[i];
    // cerr << l << ' ' << r << ' ' << mask << ' ' << who_peel << endl;
    assert(peel.count(who_peel));
    // cerr << "peel: " << peel[who_peel] << endl;
    int k = __builtin_popcount(peel[who_peel]);
    ll ans = 0;
    for (int i = mask; ; i = (i - 1) & mask) {
        if (__builtin_popcount(i) == k && __builtin_ctz(mask) == __builtin_ctz(i)) {
            // cerr << "trans: " << i << endl;
            ans += cnt_less(l, l + k - 1, i, p, peel) * cnt_tot(who_peel ^ peel[who_peel], peel);
        }

        if (i == 0) break;
    }

    int rest = mask;
    for (int i = l; i < l + k; i++) {
        if ((rest >> p[i]) & 1 ^ 1) {
            rest = -1;
            break;
        }

        rest ^= 1 << p[i];
    }

    if (rest != -1 && __builtin_ctz(rest ^ mask) == __builtin_ctz(mask)) {
        ans += cnt_less(l + k, r, rest, p, peel);
    }

    return memo_less[mask][l][r] = ans;
}

vector<int> v;
void sets_rec(const string& s, int l, int r, int prv) {
    int me = 0;
    int cnt = (r - l + 1) / 2 + 1;
    for (int i = 0; i < cnt; i++)
        me |= 1 << (prv + i);
    v.push_back(me);

    if (l > r) {
        return;
    }

    int sum = 0;
    for (int i = r; i >= l; i--) {
        if (s[i] == '1') sum++;
        else sum--;
        if (sum == 0) {
            sets_rec(s, l, i-1, prv);
            sets_rec(s, i+1, r-1, prv + (i-1 - l + 1) / 2 + 1);
            break;
        }
    }
}


vector<int> build_sets(string s, vector<int> p) { // given peel, return a list of relevant sets
    int q = sz(p);
    assert(sz(s) == 2 * (q - 1));
    v.clear();
    sets_rec(s, 0, sz(s)-1, 0);

    vector<int> ans{0};
    for (int x : v) {
        int y = 0;
        for (int i = 0; i < sz(p); i++) {
            if ((x >> i) & 1)
                y |= 1 << p[i];
        }

        ans.push_back(y);
    }

    return ans;
}

}

string aoi(int n, int m, int q, int k, vector<int> A, vector<int> B, vector<long long> C, vector<int> t, vector<int> x) {
    vector<vector<pair<int, ll>>> adj(n);
    map<pair<int, int>, int> mp;
    for (int i = 0; i < m; i++) {
        adj[A[i]].emplace_back(B[i], C[i]);
        adj[B[i]].emplace_back(A[i], C[i]);
        mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i;
    }

    vector<int> par(n, -1);
    vector<ll> dist(n, INF);
    min_pq<pair<ll, int>> pq;
    pq.push({dist[0] = 0, 0});
    while (sz(pq)) {
        auto [d_c, c] = pq.top(); pq.pop();
        if (d_c != dist[c]) continue;
        for (auto [nxt, w] : adj[c]) {
            if (dist[nxt] > dist[c] + w) {
                par[nxt] = c;
                pq.push({dist[nxt] = dist[c] + w, nxt});
            }
        }
    }

    vector<int> par_ed(n, -1);
    for (int i = 1; i < n; i++) {
        par_ed[i] = mp[{i, par[i]}];
        tree[par[i]].push_back(i);
        // cerr << "par[" << i << "] = " << par[i] << ' ' << par_ed[i] << endl;
    }

    memset(mine, -1, sizeof(mine));
    for (int i = 0; i < q; i++) mine[t[i]] = i;

    vector<int> sub_mask(k);
    for (int i = 0; i < k; i++) {
        int a = A[x[i]], b = B[x[i]];
        if (par[b] != a) swap(a, b);
        if (par[b] != a) continue; // not in the tree
        sub_mask[i] = dfs_sub(b);
        // cerr << "sub_mask[" << i << "] = " << sub_mask[i] << endl;
    }

    for (int i = 0; i < k; i++) {
        for (int j = 0; j < i; j++) {
            int one = sub_mask[i], two = sub_mask[j];
            if (one < two) swap(one, two);
            assert((one & two) == 0 || (one & two) == two);
        }
    }

    vector<int> masks = sub_mask;
    sort(masks.begin(), masks.end(), [&](int x, int y) {
        return make_pair(__builtin_popcount(x), x) < make_pair(__builtin_popcount(y), y);
    });

    masks.resize(unique(masks.begin(), masks.end()) - masks.begin());


    vector<pair<int, vector<int>>> groups;
    for (int i = 0; i < q; i++) {
        groups.push_back({1 << i, {i}});
    }

    map<int, int> peel;
    for (int x : masks) {
        // cerr << "mask: " << x << endl;
        vector<vector<int>> use;
        auto new_groups = groups; new_groups.clear();
        sort(groups.begin(), groups.end(), [&](auto one, auto two) { return one.second < two.second; });

        int left = x;
        for (auto [y, v] : groups) {
            if ((y & x) == y) {
                use.push_back(v);

                // if (left != y) cerr << "add peel: " << left << ' ' << y << endl;
                if (left != y) peel[left] = y;
                left ^= y;
            } else {
                new_groups.push_back({y, v});
            }
        }

        assert(left == 0);
        vector<int> me;
        for (auto v : use) for (int y : v) me.push_back(y);
        new_groups.push_back({x, me});
        
        swap(groups, new_groups);
    }

    vector<int> p;
    int left = (1 << q) - 1;
    sort(groups.begin(), groups.end(), [&](auto one, auto two) { return one.second < two.second; });
    for (auto [y, v] : groups) {
        // if (left != y) cerr << "add peel: " << left << ' ' << y << endl;
        if (left != y) peel[left] = y;
        left ^= y;
        for (int x : v) p.push_back(x);
    }
    assert(left == 0);

    /*
    cerr << "p: ";
    for (int x : p) cerr << x << ' ';
    cerr << endl;
    */

    memset(memo_less, -1, sizeof(memo_less));
    memset(memo_tot, -1, sizeof(memo_tot));
    fact[0] = 1;
    for (int i = 1; i <= Q; i++)
        fact[i] = fact[i-1] * i;

    ll tot_cnt = cnt_tot((1 << q) - 1, peel);
    // cerr << "tot_cnt: " << tot_cnt << endl;
    ll perm_idx = cnt_less(0, q-1, (1 << q) - 1, p, peel);
    // cerr << "perm_idx: " << perm_idx << endl;

    const int BITS = 40;
    assert(perm_idx < tot_cnt);
    assert(tot_cnt < (1LL << BITS));
    string s_tree = build_tree((1 << q) - 1, peel);
    // cerr << s_tree << endl;
    string ans = enc(perm_idx, BITS) + s_tree;

    auto st = build_sets(s_tree, p);
    /*
    cerr << "st: "; for (int x : st) cerr << x << ' ';
    cerr << endl;
    */

    assert(sz(st) <= 32);
    for (int i = 0; i < k; i++) {
        int me = sub_mask[i];
        int use = -1;
        for (int j = 0; j < sz(st); j++) {
            if (st[j] == me) {
                use = j;
                break;
            }
        }

        assert(use != -1);
        ans += enc(use, 5);
    }

    return ans;
}

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;

namespace {

const ll INF = 1e18+10;
const int N = 2e4+10, Q = 16;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

ll dec(string s) {
    reverse(s.begin(), s.end());

    ll ans = 0;
    for (char c : s) {
        ans *= 2;
        ans += c - '0';
    }
    return ans;
}

ll memo_ways[3 * Q][3 * Q];
ll fact[Q+1];

ll nck(int n, int k) { 
    assert(n >= k);
    return fact[n] / fact[k] / fact[n-k];
}


int need[Q];

void build_need(const string& s, int l, int r, int prv) {
    int me = 0;
    int cnt = (r - l + 1) / 2 + 1;
    if (l > r) {
        return;
    }

    int sum = 0;
    for (int i = r; i >= l; i--) {
        if (s[i] == '1') sum++;
        else sum--;
        if (sum == 0) {
            int nxt_prv = prv + (i-1 - l + 1) / 2 + 1;
            need[prv] |= 1 << nxt_prv;
            // cerr << "need: " << prv << ' ' << nxt_prv << endl;
            build_need(s, l, i-1, prv);
            build_need(s, i+1, r-1, nxt_prv);
            break;
        }
    }
}

ll get_cnt(vector<int> p) {
    int q = sz(p);
    vector<int> loc(q, -1);
    for (int i = 0; i < q; i++) {
        if (p[i] != -1) {
            loc[p[i]] = i;
        }
    }

    vector<ll> pdp(1 << q); pdp[0] = 1;
    for (int rep = 0; rep < q; rep++) {
        vector<ll> ndp(1 << q);
        for (int mask = 0; mask < (1 << q); mask++) if (pdp[mask]) { 
            for (int j = 0; j < q; j++) if ((mask >> j) & 1 ^ 1) {
                if (loc[rep] != -1 && j != loc[rep]) continue;
                if (need[j] & mask) continue;
                ndp[mask | (1 << j)] += pdp[mask];
            }
        }
        swap(pdp, ndp);
    }

    return pdp[(1 << q) - 1];
}

vector<int> build_perm(ll perm_idx, string s_tree) {
    int q = sz(s_tree) / 2 + 1;
    build_need(s_tree, 0, sz(s_tree)-1, 0);

    vector<int> p(q, -1);
    vector<bool> used(q, 0);
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < q; j++) if (!used[j]) {
            p[i] = j;
            ll cur = get_cnt(p);
            if (cur > perm_idx) {
                used[j] = 1;
                break;
            } else {
                perm_idx -= cur;
            }
        }
    }

    assert(perm_idx == 0);
    return p;
}

vector<int> v;
void sets_rec(const string& s, int l, int r, int prv) {
    int me = 0;
    int cnt = (r - l + 1) / 2 + 1;
    for (int i = 0; i < cnt; i++)
        me |= 1 << (prv + i);
    v.push_back(me);

    if (l > r) {
        return;
    }

    int sum = 0;
    for (int i = r; i >= l; i--) {
        if (s[i] == '1') sum++;
        else sum--;
        if (sum == 0) {
            sets_rec(s, l, i-1, prv);
            sets_rec(s, i+1, r-1, prv + (i-1 - l + 1) / 2 + 1);
            break;
        }
    }
}


vector<int> build_sets(string s, vector<int> p) { // given peel, return a list of relevant sets
    int q = sz(p);
    assert(sz(s) == 2 * (q - 1));
    v.clear();
    sets_rec(s, 0, sz(s)-1, 0);

    vector<int> ans{0};
    for (int x : v) {
        int y = 0;
        for (int i = 0; i < sz(p); i++) {
            if ((x >> i) & 1)
                y |= 1 << p[i];
        }

        ans.push_back(y);
    }

    return ans;
}
}


void bitaro(int n, int m, int q, int k, vector<int> A, vector<int> B, vector<long long> C, vector<int> t, vector<int> x, string s) {
    fact[0] = 1;
    for (int i = 1; i <= Q; i++) {
        fact[i] = fact[i-1] * i;
    }

    const int BITS = 40;
    ll perm_idx = dec(s.substr(0, BITS));
    string s_tree = s.substr(BITS, 2 * (q - 1));
    string rest = s.substr(BITS + 2 * (q - 1));

    // cerr << s_tree << ' ' << perm_idx << endl;
    vector<int> p = build_perm(perm_idx, s_tree);
    /*
    cerr << "bitaro p: "; for (int x : p) cerr << x << ' ';
    cerr << endl;
    */
    auto st = build_sets(s_tree, p);
    /*
    cerr << "bitaro st: ";
    for (int x : st) cerr << x << ' ';
    cerr << endl;
    */

    vector<vector<int>> mine(q);
    for (int i = 0; i < k; i++) {
        int mask = st[dec(rest.substr(i * 5, 5))];
        // cerr << "sub_mask[" << i << "] = " << mask << endl;
        for (int j = 0; j < q; j++) {
            if ((mask >> j) & 1) {
                mine[j].push_back(i);
            }
        }
    }

    map<pair<int, int>, int> mp;
    for (int i = 0; i < m; i++) {
        mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i;
    }

    for (int i = 0; i < q; i++) {
        auto rC = C;
        for (int e : x) rC[e] = INF;
        for (int e : mine[i]) {
            rC[x[e]] = 0;
            // cerr << "use: " << e << endl;
        }
        // cerr << "start" << endl;

        vector<vector<pair<int, ll>>> adj(n);
        for (int i = 0; i < m; i++) {
            adj[A[i]].emplace_back(B[i], rC[i]);
            adj[B[i]].emplace_back(A[i], rC[i]);
        }

        vector<int> par(n, -1);
        vector<ll> dist(n, INF);
        min_pq<pair<ll, int>> pq;
        pq.push({dist[0] = 0, 0});
        while (sz(pq)) {
            auto [d_c, c] = pq.top(); pq.pop();
            if (d_c != dist[c]) continue;
            for (auto [nxt, w] : adj[c]) {
                if (dist[nxt] > dist[c] + w) {
                    // cerr << "new_par: " << nxt << ' ' << c << endl;
                    par[nxt] = c;
                    pq.push({dist[nxt] = dist[c] + w, nxt});
                }
            }
        }

        // cerr << "building from: " << t[i] << endl;
        vector<int> ans{t[i]};
        while (ans.back() != 0) ans.push_back(par[ans.back()]);
        reverse(ans.begin(), ans.end());

        /*
        cerr << "nodes: ";
        for (int x : ans) cerr << x << ' ';
        cerr << endl;
        */

        vector<int> real;
        for (int i = 1; i < sz(ans); i++) real.push_back(mp[{ans[i-1], ans[i]}]);
        answer(real);

        // cerr << "done answer\n";
    }
}

Compilation message

Aoi.cpp: In function 'll {anonymous}::cnt_less(int, int, int, const std::vector<int>&, std::map<int, int>&)':
Aoi.cpp:82:28: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   82 |         if ((rest >> p[i]) & 1 ^ 1) {
      |             ~~~~~~~~~~~~~~~^~~

Bitaro.cpp: In function 'void {anonymous}::build_need(const string&, int, int, int)':
Bitaro.cpp:40:9: warning: unused variable 'me' [-Wunused-variable]
   40 |     int me = 0;
      |         ^~
Bitaro.cpp:41:9: warning: unused variable 'cnt' [-Wunused-variable]
   41 |     int cnt = (r - l + 1) / 2 + 1;
      |         ^~~
Bitaro.cpp: In function 'll {anonymous}::get_cnt(std::vector<int>)':
Bitaro.cpp:74:57: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   74 |             for (int j = 0; j < q; j++) if ((mask >> j) & 1 ^ 1) {
      |                                             ~~~~~~~~~~~~^~~
Bitaro.cpp: At global scope:
Bitaro.cpp:31:4: warning: 'll {anonymous}::nck(int, int)' defined but not used [-Wunused-function]
   31 | ll nck(int n, int k) {
      |    ^~~
Bitaro.cpp:28:4: warning: '{anonymous}::memo_ways' defined but not used [-Wunused-variable]
   28 | ll memo_ways[3 * Q][3 * Q];
      |    ^~~~~~~~~

Subtask #1
99.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 141692 KB Output is correct
2 Correct 53 ms 133036 KB Output is correct
3 Partially correct 239 ms 142368 KB Partially correct
4 Correct 313 ms 141528 KB Output is correct
5 Partially correct 152 ms 142480 KB Partially correct
6 Partially correct 238 ms 142144 KB Partially correct
7 Partially correct 257 ms 142448 KB Partially correct
8 Partially correct 165 ms 142212 KB Partially correct
9 Partially correct 272 ms 141196 KB Partially correct
10 Correct 98 ms 141740 KB Output is correct
11 Partially correct 262 ms 142180 KB Partially correct
12 Correct 212 ms 142284 KB Output is correct
13 Correct 177 ms 142352 KB Output is correct
14 Correct 152 ms 142232 KB Output is correct
15 Correct 217 ms 141564 KB Output is correct
16 Correct 87 ms 141228 KB Output is correct
17 Partially correct 271 ms 141412 KB Partially correct
18 Partially correct 288 ms 141232 KB Partially correct
19 Partially correct 143 ms 142824 KB Partially correct
20 Correct 112 ms 142936 KB Output is correct
21 Partially correct 148 ms 142948 KB Partially correct
22 Partially correct 163 ms 142888 KB Partially correct
23 Correct 125 ms 142804 KB Output is correct
24 Partially correct 156 ms 142924 KB Partially correct
25 Partially correct 279 ms 141444 KB Partially correct
26 Partially correct 258 ms 141308 KB Partially correct
27 Correct 114 ms 134048 KB Output is correct
28 Correct 209 ms 142332 KB Output is correct
29 Partially correct 217 ms 139200 KB Partially correct
30 Correct 272 ms 142708 KB Output is correct
31 Correct 126 ms 142440 KB Output is correct
32 Correct 199 ms 142716 KB Output is correct
33 Correct 154 ms 141980 KB Output is correct
34 Correct 163 ms 142496 KB Output is correct
35 Correct 278 ms 142868 KB Output is correct
36 Correct 284 ms 142800 KB Output is correct
37 Correct 93 ms 137800 KB Output is correct
38 Partially correct 247 ms 139576 KB Partially correct
39 Correct 309 ms 139180 KB Output is correct
40 Correct 98 ms 138704 KB Output is correct
41 Partially correct 216 ms 142772 KB Partially correct
42 Correct 132 ms 142948 KB Output is correct
43 Correct 153 ms 142988 KB Output is correct
44 Correct 106 ms 143020 KB Output is correct
45 Correct 95 ms 137824 KB Output is correct
46 Partially correct 199 ms 138772 KB Partially correct
47 Correct 185 ms 138636 KB Output is correct
48 Correct 65 ms 133344 KB Output is correct
49 Correct 57 ms 133044 KB Output is correct
50 Correct 88 ms 141328 KB Output is correct
51 Partially correct 75 ms 134440 KB Partially correct
52 Correct 145 ms 134240 KB Output is correct
53 Correct 124 ms 141476 KB Output is correct
54 Partially correct 83 ms 138412 KB Partially correct
55 Correct 129 ms 139420 KB Output is correct
56 Correct 123 ms 142600 KB Output is correct
57 Partially correct 138 ms 142664 KB Partially correct
58 Partially correct 141 ms 140452 KB Partially correct
59 Correct 160 ms 143004 KB Output is correct
60 Partially correct 160 ms 142732 KB Partially correct
61 Correct 165 ms 142604 KB Output is correct
62 Correct 154 ms 142092 KB Output is correct
63 Correct 170 ms 142972 KB Output is correct
64 Correct 93 ms 141084 KB Output is correct
65 Correct 117 ms 138988 KB Output is correct
66 Correct 114 ms 143020 KB Output is correct
67 Correct 113 ms 138920 KB Output is correct
68 Correct 112 ms 143012 KB Output is correct
69 Correct 70 ms 133296 KB Output is correct
70 Correct 57 ms 133036 KB Output is correct
71 Correct 59 ms 133028 KB Output is correct
72 Correct 80 ms 137360 KB Output is correct
73 Partially correct 132 ms 138408 KB Partially correct
74 Partially correct 129 ms 138296 KB Partially correct
75 Correct 79 ms 138260 KB Output is correct
76 Correct 59 ms 133052 KB Output is correct
77 Correct 151 ms 142292 KB Output is correct
78 Partially correct 169 ms 142600 KB Partially correct
79 Correct 168 ms 142396 KB Output is correct
80 Correct 60 ms 133108 KB Output is correct
81 Correct 147 ms 142364 KB Output is correct
82 Partially correct 228 ms 142204 KB Partially correct
83 Correct 236 ms 142176 KB Output is correct