fork download
copy 
  1. #include <vector>
  2. #include <string>
  3. #include <algorithm>
  4. #include <iostream>
  5. using namespace std;
  6. int dy[32][16];
  7. int dyn[32];
  8. int r[32][32][2];
  9. #define INF 10000000
  10. class History{
  11. public:
  12.   string verifyClaims(vector <string> dynasties, vector <string> battles, vector <string> queries){
  13.     int N = dynasties.size();
  14.     // parse
  15.     for( int i=0; i<N; i++ ){
  16.       int idx=0;
  17.       string& s = dynasties[i];
  18.       for( int j=0; j<s.size(); j++ ){
  19.         if( s[j] == ' ' ) idx++;
  20.         else dy[i][idx] = dy[i][idx]*10 + s[j] - '0';
  21.       }
  22.       dyn[i] = idx + 1;
  23.     }
  24.     // analyse
  25.     string bs;
  26.     for( int i=0; i<N; i++ ) for( int j=0; j<N; j++ ){
  27.       if( i==j ){ r[i][j][0] = 0;    r[i][j][1] = 0;   }
  28.       else      { r[i][j][0] = -INF; r[i][j][1] = INF; }
  29.     }
  30.     for( int i=0; i<battles.size(); i++ ) bs += battles[i];
  31.     for( int i=0; i<bs.size(); i += 6 ){
  32.       int c0 = bs[i  ] - 'A'; int y0 = bs[i+1] - '0';
  33.       int c1 = bs[i+3] - 'A'; int y1 = bs[i+4] - '0';
  34.       r[c0][c1][0] = max( r[c0][c1][0], dy[c1][y1] - (dy[c0][y0+1]-1) );
  35.       r[c0][c1][1] = min( r[c0][c1][1], (dy[c1][y1+1]-1) - dy[c0][y0] );
  36.       r[c1][c0][0] = max( r[c1][c0][0], -r[c0][c1][1] );
  37.       r[c1][c0][1] = min( r[c1][c0][1], -r[c0][c1][0] );
  38.     }
  39.     for( int i=0; i<N; i++ ){
  40.       for( int j=0; j<N; j++ ){
  41.         if( j==i ) continue;
  42.         for( int k=0; k<N; k++ ){
  43.           if( k==i || j==k ) continue;
  44.           r[j][k][0] = max( r[j][k][0], r[j][i][0] + r[i][k][0] );
  45.           r[j][k][1] = min( r[j][k][1], r[j][i][1] + r[i][k][1] );
  46.         }
  47.       }
  48.     }
  49.     // query
  50.     string ret;
  51.     for( int i=0; i<queries.size(); i++ ){
  52.       string& s = queries[i];
  53.       int c0 = s[0] - 'A'; int y0 = s[1] - '0';
  54.       int c1 = s[3] - 'A'; int y1 = s[4] - '0';
  55.       int r0 = dy[c1][y1] - (dy[c0][y0+1]-1);
  56.       int r1 = (dy[c1][y1+1]-1) - dy[c0][y0];
  57.       if( r1 < r[c0][c1][0] || r0 > r[c0][c1][1] ) ret += "N";
  58.       else ret+= "Y";
  59.     }
  60.     return ret;
  61.   }
  62. };
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/id5TUL
language:
C++ (gcc 8.3)
created:
10 years 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!