fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pp push_back
  5. #define endl '\n'
  6. #define all(x) x.begin(),x.end()
  7. #define ld long double
  8. #define PI acos(-1)
  9. #define sin(a) sin((a)*PI/180)
  10. #define cos(a) cos((a)*PI/180)
  11. #define ones(x) __builtin_popcountll(x)
  12. //#define int ll
  13.  
  14. using namespace std;
  15.  
  16. void Drakon() {
  17.     ios_base::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.     cout.tie(nullptr);
  20. #ifdef Clion
  21.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  22. #endif
  23. }
  24.  
  25. unsigned long long inf = 1e10;
  26. const double EPS = 1e-6;
  27. int MOD = 1000000007, N = 200005, LOG = 25;
  28.  
  29. ll mul(const ll &a, const ll &b) {
  30.     return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
  31. }
  32.  
  33. ll add(const ll &a, const ll &b) {
  34.     return (a + b + 2 * MOD) % MOD;
  35. }
  36.  
  37. ll pw(ll x, ll y) {
  38.     ll ret = 1;
  39.     while (y > 0) {
  40.         if (y % 2 == 0) {
  41.             x = mul(x, x);
  42.             y = y / 2;
  43.         } else {
  44.             ret = mul(ret, x);
  45.             y = y - 1;
  46.         }
  47.     }
  48.     return ret;
  49. }
  50.  
  51. #define rep(aa, bb, cc) for(int aa = bb; aa < cc;aa++)
  52. struct Dinic {
  53.     struct Edge {
  54.         int to, rev;
  55.         ll c, oc;
  56.         ll flow() { return max(oc - c, 0LL); } // if you need flows
  57.     };
  58.     vector<int> lvl, ptr, q;
  59.     vector<vector<Edge>> adj;
  60.     Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
  61.     void addEdge(int a, int b, ll c, ll rcap = 0) {
  62.         adj[a].push_back({b, (int)adj[b].size(), c, c});
  63.         adj[b].push_back({a, (int)adj[a].size() - 1, rcap, rcap});
  64.     }
  65.     ll dfs(int v, int t, ll f) {
  66.         if (v == t || !f) return f;
  67.         for (int& i = ptr[v]; i < (int)adj[v].size(); i++) {
  68.             Edge& e = adj[v][i];
  69.             if (lvl[e.to] == lvl[v] + 1)
  70.                 if (ll p = dfs(e.to, t, min(f, e.c))) {
  71.                     e.c -= p, adj[e.to][e.rev].c += p;
  72.                     return p;
  73.                 }
  74.         }
  75.         return 0;
  76.     }
  77.     ll calc(int s, int t) {
  78.         ll flow = 0; q[0] = s;
  79.         rep(L,0,31) do { // 'int L=30' maybe faster for random data
  80.                 lvl = ptr = vector<int>((int)q.size());
  81.                 int qi = 0, qe = lvl[s] = 1;
  82.                 while (qi < qe && !lvl[t]) {
  83.                     int v = q[qi++];
  84.                     for (Edge e : adj[v])
  85.                         if (!lvl[e.to] && e.c >> (30 - L))
  86.                             q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
  87.                 }
  88.                 while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
  89.             } while (lvl[t]);
  90.         return flow;
  91.     }
  92.     bool leftOfMinCut(int a) { return lvl[a] != 0; }
  93. };
  94.  
  95. vector<int> can;
  96. bool vis[505];
  97. int n, k, m, possible[505];
  98.  
  99. void dfs(int u) {
  100.     if(vis[u])return;
  101.     vis[u] = true;
  102.     can.push_back(u);
  103.  
  104.     for (int i = 0; i < m; ++i) {
  105.         if(~possible[i])
  106.             dfs((u + i) % m);
  107.     }
  108. }
  109.  
  110. vector<int> cur, path;
  111.  
  112. void getPath(int u, int want){
  113.     if(vis[u])return;
  114.     vis[u] = true;
  115.     if(u == want) {
  116.         path = cur;
  117.         return;
  118.     }
  119.  
  120.     for (int i = 0; i < m; ++i) {
  121.         if(~possible[i]){
  122.             cur[possible[i]] ++;
  123.             getPath((u + i) % m, want);
  124.             cur[possible[i]] --;
  125.         }
  126.     }
  127. }
  128.  
  129. void solve() {
  130.     cin >> n >> k >> m;
  131.     MOD = m;
  132.     char c[n][k];
  133.     for (int i = 0; i < n; ++i) {
  134.         for (int j = 0; j < k; ++j) {
  135.             cin >> c[i][j];
  136.         }
  137.     }
  138.  
  139.     Dinic dinic(n + m + 2);
  140.     int s = n + m, e = n + m + 1;
  141.     for (int i = 0; i < n; ++i) {
  142.         can.clear();
  143.         for (int j = 0; j < m; ++j) {
  144.             vis[j] = false;
  145.             possible[j] = -1;
  146.         }
  147.         for (int j = 0; j < k; ++j) {
  148.             possible[pw(c[i][j] - 'a' + 1, j + 1)] = j;
  149.         }
  150.  
  151.         dfs(0);
  152.  
  153.         dinic.addEdge(s, i, 1);
  154.         for (int j = 0; j < can.size(); ++j) {
  155.             dinic.addEdge(i, n + can[j], 1);
  156.         }
  157.     }
  158.  
  159.     for (int i = 0; i < m; ++i) {
  160.         dinic.addEdge(n + i, e, 1);
  161.     }
  162.  
  163.     int mx = dinic.calc(s, e);
  164.     if(mx < n){
  165.         cout << "No\n";
  166.         return;
  167.     }
  168.  
  169.     cout << "Yes\n";
  170.     for (int i = 0; i < n; ++i) {
  171.  
  172.         for (int j = 0; j < m; ++j) {
  173.             vis[j] = false;
  174.             possible[j] = -1;
  175.         }
  176.         for (int j = 0; j < k; ++j) {
  177.             possible[pw(c[i][j] - 'a' + 1, j + 1)] = j;
  178.         }
  179.  
  180.         for(auto md : dinic.adj[i]){
  181.             if(md.c == 0){
  182.                 path.clear();
  183.                 cur = vector<int>(k);
  184.                 getPath(0, md.to - n);
  185.                 break;
  186.             }
  187.         }
  188.  
  189.         for(auto x : path){
  190.             cout << x << ' ';
  191.         }
  192.         cout << endl;
  193.     }
  194. }
  195.  
  196. signed main() {
  197.     Drakon();
  198.     freopen("hash.in", "r", stdin);
  199.     int t = 1;
  200.     cin >> t;
  201.     while (t--) {
  202.         solve();
  203.     }
  204. }
Success #stdin #stdout 0.01s 5256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Yes
https://ideone.com/UYOuK3
language:
C++14 (gcc 8.3)
created:
28 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!