#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 = 30;
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 = 30;
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];
| ^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
105 ms |
141280 KB |
Output is correct |
| 2 |
Correct |
68 ms |
133036 KB |
Output is correct |
| 3 |
Runtime error |
194 ms |
278096 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
