Advertisement
Josif_tepe

Untitled

Mar 19th, 2023
767
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. int n, m;
  7. vector<pair<int, char>> graph[105];
  8. int dp[105][105][30][2];
  9. // +INF -- max win
  10. // -INF -- lucas win
  11. int rec(int max_node, int lucas_node, int last_char, int turn) {
  12.     if(dp[max_node][lucas_node][last_char][turn] != -1) {
  13.         return dp[max_node][lucas_node][last_char][turn];
  14.     }
  15.     int result;
  16.     if(turn == 0) {
  17.         result = -(2e9);
  18.         for(int i = 0; i < graph[max_node].size(); i++) {
  19.             int neighbour = graph[max_node][i].first;
  20.             int val = (int) graph[max_node][i].second;
  21.            
  22.             if(last_char <= val) {
  23.                 result = max(result, rec(neighbour, lucas_node, val, 1));
  24.             }
  25.         }
  26.     }
  27.     else {
  28.         result = (2e9);
  29.         for(int i = 0; i < graph[lucas_node].size(); i++) {
  30.             int neighbour = graph[lucas_node][i].first;
  31.             int val = (int) graph[lucas_node][i].second;
  32.            
  33.             if(last_char <= val) {
  34.                 result = min(result, rec(max_node, neighbour, val, 0));
  35.             }
  36.         }
  37.     }
  38.     return dp[max_node][lucas_node][last_char][turn] = result;
  39. }
  40. int main() {
  41.     ios_base::sync_with_stdio(false);
  42.     cin >> n >> m;
  43.     for(int i = 0; i < m; i++) {
  44.         int a, b;
  45.         char c;
  46.         cin >> a >> b >> c;
  47.         a--; b--;
  48.         graph[a].push_back(make_pair(b, (c - 'a') + 1));
  49.     }
  50.     memset(dp, -1, sizeof dp);
  51.     for(int i = 0; i < n; i++) {
  52.         for(int j = 0; j < n; j++) {
  53.             if(rec(i, j, 0, 0) == 2e9) {
  54.                 cout << "A";
  55.             }
  56.             else {
  57.                 cout << "B";
  58.             }
  59.         }
  60.         cout << endl;
  61.     }
  62.    return 0;
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement