Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- #define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
- #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
- #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
- #define all(a) (a).begin(), (a).end()
- #define sz(a) int((a).size())
- #define pb(a) push_back(a)
- #define mp(x, y) make_pair((x), (y))
- #define x first
- #define y second
- using namespace std;
- typedef long long li;
- typedef long double ld;
- typedef pair<int, int> pt;
- template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
- template<typename X> inline X sqr(const X& a) { return a * a; }
- template<typename A, typename B> inline ostream& operator<< (ostream& out, const pair<A, B>& p) { return out << "(" << p.x << ", " << p.y << ")"; }
- 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 << " ]"; }
- template<typename T> inline ostream& operator<< (ostream& out, const set<T>& a) { return out << vector<T>(all(a)); }
- template<typename T> inline ostream& operator<< (ostream& out, pair<T*, int> a) { return out << vector<T>(a.x, a.x + a.y); }
- inline ld gett() { return clock() / ld(CLOCKS_PER_SEC); }
- const int INF = int(1e9);
- const li INF64 = li(1e18);
- const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
- const int N = 2525, LOGN = 15;
- int n, a[N][N];
- bool read() {
- if (!(cin >> n)) return false;
- forn(i, n) forn(j, n) assert(scanf("%d", &a[i][j]) == 1);
- return true;
- }
- int tt, tin[N], tout[N];
- vector<int> g[N];
- void dfs(int v) {
- tin[v] = tt++;
- forn(i, sz(g[v])) dfs(g[v][i]);
- tout[v] = tt;
- }
- inline bool parent(int a, int b) { return tin[a] <= tin[b] && tout[b] <= tout[a]; }
- int p[LOGN][N], pd[LOGN][N];
- int d[N], pr[N];
- bool used[N];
- int calc(int a, int b) {
- int ans = 0;
- nfor(i, LOGN) {
- if (!parent(p[i][a], b)) {
- ans = max(ans, pd[i][a]);
- a = p[i][a];
- }
- if (!parent(p[i][b], a)) {
- ans = max(ans, pd[i][b]);
- b = p[i][b];
- }
- }
- if (!parent(a, b)) ans = max(ans, pd[0][a]);
- if (!parent(b, a)) ans = max(ans, pd[0][b]);
- return ans;
- }
- void solve() {
- forn(i, n)
- forn(j, n)
- if (a[i][j] != a[j][i] || (i == j && a[i][j])) {
- puts("NOT MAGIC");
- return;
- }
- forn(i, n) {
- used[i] = false;
- d[i] = INT_MAX;
- g[i].clear();
- }
- d[0] = 0;
- pr[0] = -1;
- forn(i, n) {
- int v = -1;
- forn(j, n)
- if (!used[j] && (v == -1 || d[v] > d[j]))
- v = j;
- assert(v != -1);
- used[v] = true;
- //cerr << "v=" << v << " p[v]=" << pr[v] << endl;
- if (pr[v] != -1) {
- p[0][v] = pr[v];
- pd[0][v] = a[pr[v]][v];
- g[pr[v]].pb(v);
- } else {
- p[0][v] = v;
- pd[0][v] = 0;
- }
- forn(j, n)
- if (!used[j] && d[j] > a[v][j]) {
- d[j] = a[v][j];
- pr[j] = v;
- }
- }
- //cerr << mp(pr, n) << endl;
- tt = 0;
- dfs(0);
- fore(i, 1, LOGN)
- forn(j, n) {
- p[i][j] = p[i - 1][p[i - 1][j]];
- pd[i][j] = max(pd[i - 1][j], pd[i - 1][p[i - 1][j]]);
- }
- forn(i, n)
- forn(j, n)
- if (a[i][j] != calc(i, j)) {
- puts("NOT MAGIC");
- return;
- }
- puts("MAGIC");
- }
- int main() {
- #ifdef SU1
- assert(freopen("input.txt", "rt", stdin));
- //assert(freopen("output.txt", "wt", stdout));
- #endif
- cout << setprecision(10) << fixed;
- cerr << setprecision(5) << fixed;
- while (read()) {
- ld stime = gett();
- solve();
- cerr << "Time: " << gett() - stime << endl;
- //break;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement