|
|
back to boardaccepted Posted by Mikhail 19 Sep 2018 14:24 //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; const int maxn = 100; vi g[maxn]; int n, a, d; void read() { string str; cin >> n >> d >> a; for (int i = 0; i < n; ++i) { cin >> str; for (int j = 0; j < n; ++j) { if (str[j] == '1') { g[i].pb(j); } } } } int last = -1; bool was[maxn]; ll money = 0; vii add, del; void dfs1 (int v) { last = v; was[v] = true; for (int j : g[v]) { if (!was[j]) dfs1(j); } } void step1() { memset(was, false, n); dfs1(0); for (int i = 0; i < n; ++i) { if (!was[i]) { money += a; g[i].pb(last); g[last].pb(i); add.eb(i, last); dfs1(i); } } } void dfs2 (int v, int pr = -1) { was[v] = true; for (int j : g[v]) { if (j != pr) { if (!was[j]) { dfs2(j, v); } else { del.eb(min(v, j), max(v, j)); } } } } void step2() { memset(was, false, n); dfs2(0); } string ans[maxn]; void make_ans() { read(); string str; for (int i = 0; i < n; ++i) str += '0'; for (int i = 0; i < n; ++i) ans[i] = str; step1(); step2(); sort(all(del)); unique(del); money += (ll)del.size() * d; for (ii j : del) ans[j.fi][j.se] = ans[j.se][j.fi] = 'd'; for (ii j : add) ans[j.fi][j.se] = ans[j.se][j.fi] = 'a'; } int main() { make_ans(); cout << money << '\n'; for (int i = 0; i < n; ++i) cout << ans[i] << '\n'; return 0; } |
|
|