Advertisement
edvard_davtyan

Untitled

Mar 1st, 2016
1,230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. template<typename A, typename B> inline ostream& operator<< (ostream& out, const pair<A, B>& p) { return out << "(" << p.x << ", " << p.y << ")"; }
  24. template<typename T> inline ostream& operator<< (ostream& out, const vector<T>& a) { out << "["; forn(i, sz(a)) { if (i) out << ','; out << ' ' << a[i]; } return out << " ]"; }
  25. template<typename T> inline ostream& operator<< (ostream& out, const set<T>& a) { return out << vector<T>(all(a)); }
  26. template<typename T> inline ostream& operator<< (ostream& out, pair<T*, int> a) { return out << vector<T>(a.x, a.x + a.y); }
  27.  
  28. inline ld gett() { return clock() / ld(CLOCKS_PER_SEC); }
  29.  
  30. const int INF = int(1e9);
  31. const li INF64 = li(1e18);
  32. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  33.  
  34. const int N = 2525, LOGN = 15;
  35.  
  36. int n, a[N][N];
  37.  
  38. bool read() {
  39.     if (!(cin >> n)) return false;
  40.     forn(i, n) forn(j, n) assert(scanf("%d", &a[i][j]) == 1);
  41.     return true;
  42. }
  43.  
  44. int tt, tin[N], tout[N];
  45. vector<int> g[N];
  46.  
  47. void dfs(int v) {
  48.     tin[v] = tt++;
  49.     forn(i, sz(g[v])) dfs(g[v][i]);
  50.     tout[v] = tt;
  51. }
  52.  
  53. inline bool parent(int a, int b) { return tin[a] <= tin[b] && tout[b] <= tout[a]; }
  54.  
  55. int p[LOGN][N], pd[LOGN][N];
  56.  
  57. int d[N], pr[N];
  58. bool used[N];
  59.  
  60. int calc(int a, int b) {
  61.     int ans = 0;
  62.     nfor(i, LOGN) {
  63.         if (!parent(p[i][a], b)) {
  64.             ans = max(ans, pd[i][a]);
  65.             a = p[i][a];
  66.         }
  67.         if (!parent(p[i][b], a)) {
  68.             ans = max(ans, pd[i][b]);
  69.             b = p[i][b];
  70.         }
  71.     }
  72.     if (!parent(a, b)) ans = max(ans, pd[0][a]);
  73.     if (!parent(b, a)) ans = max(ans, pd[0][b]);
  74.     return ans;
  75. }
  76.  
  77. void solve() {
  78.     forn(i, n)
  79.         forn(j, n)
  80.             if (a[i][j] != a[j][i] || (i == j && a[i][j])) {
  81.                 puts("NOT MAGIC");
  82.                 return;
  83.             }
  84.  
  85.     forn(i, n) {
  86.         used[i] = false;
  87.         d[i] = INT_MAX;
  88.         g[i].clear();
  89.     }
  90.  
  91.     d[0] = 0;
  92.     pr[0] = -1;
  93.     forn(i, n) {
  94.         int v = -1;
  95.         forn(j, n)
  96.             if (!used[j] && (v == -1 || d[v] > d[j]))
  97.                 v = j;
  98.  
  99.         assert(v != -1);
  100.         used[v] = true;
  101.         //cerr << "v=" << v << " p[v]=" << pr[v] << endl;
  102.  
  103.         if (pr[v] != -1) {
  104.             p[0][v] = pr[v];
  105.             pd[0][v] = a[pr[v]][v];
  106.             g[pr[v]].pb(v);
  107.         } else {
  108.             p[0][v] = v;
  109.             pd[0][v] = 0;
  110.         }
  111.  
  112.         forn(j, n)
  113.             if (!used[j] && d[j] > a[v][j]) {
  114.                 d[j] = a[v][j];
  115.                 pr[j] = v;
  116.             }
  117.     }
  118.  
  119.     //cerr << mp(pr, n) << endl;
  120.  
  121.     tt = 0;
  122.     dfs(0);
  123.  
  124.     fore(i, 1, LOGN)
  125.         forn(j, n) {
  126.             p[i][j] = p[i - 1][p[i - 1][j]];
  127.             pd[i][j] = max(pd[i - 1][j], pd[i - 1][p[i - 1][j]]);
  128.         }
  129.  
  130.     forn(i, n)
  131.         forn(j, n)
  132.             if (a[i][j] != calc(i, j)) {
  133.                 puts("NOT MAGIC");
  134.                 return;
  135.             }
  136.     puts("MAGIC");
  137. }
  138.  
  139. int main() {
  140. #ifdef SU1
  141.     assert(freopen("input.txt", "rt", stdin));
  142.     //assert(freopen("output.txt", "wt", stdout));
  143. #endif
  144.    
  145.     cout << setprecision(10) << fixed;
  146.     cerr << setprecision(5) << fixed;
  147.  
  148.     while (read()) {
  149.         ld stime = gett();
  150.         solve();
  151.         cerr << "Time: " << gett() - stime << endl;
  152.         //break;
  153.     }
  154.    
  155.     return 0;
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement