Submission #8568580

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

class SCC {
private:
  vector<vector<int>> &G;
  vector<vector<int>> &rG;
  vector<bool> used;
  vector<int> vs;
  int n;
  void dfs(int v){
    used[v] = true;
    for(auto to : G[v]) if(!used[to]) dfs(to);
    vs.pb(v);
  }
  void rdfs(int v, int k){
    used[v] = true;
    cmp[v] = k;
    groups.back().pb(v);
    for(auto to : rG[v]) if(!used[to]) rdfs(to, k);
  }
public:
  vector<int> cmp; //頂点iが属するSCCのID
  vector<vector<int>> groups; // SCCのトポロジカル順i番目に属する頂点番号群
  int gc = 0; // group count
  SCC(vector<vector<int>> &g, vector<vector<int>> &r) : G(g), rG(r){
    n = G.size();
    used = vector<bool>(n, false);
    cmp.resize(n);
    rep(i,n) if(!used[i]) dfs(i);
    fill(all(used), false);
    for(int i=vs.size()-1; i>=0; i--) if(!used[vs[i]]){
      groups.pb(vector<int>());
      rdfs(vs[i], gc++);
    }
  }
  inline bool same(int i, int j){ return cmp[i]==cmp[j]; }
  inline int operator[](int i){ return cmp[i]; }
};

int main(){
  int n;
  cin>>n;
  map<pair<int,int>, int> num;
  rep(i,n) rep(j,i) {
    int x = num.size();
    num[{j,i}] = x;
  }

  vector<vector<int>> to(num.size());
  vector<vector<int>> from(num.size());

  rep(i,n){
    vector<int> tmp;
    rep(j,n-1){
      int k; cin>>k;
      k--;
      tmp.pb(num[{min(i,k), max(i,k)}]);
    }
    rep(j,n-2) {
      to[tmp[j]].pb(tmp[j+1]);
      from[tmp[j+1]].pb(tmp[j]);
    }
  }

  // SCC scc(to, from);

  // for(auto &v : scc.groups) if(v.size() > 1) {
  //   cout << -1 << endl;
  //   return 0;
  // }

  vector<int> nxt;
  vector<int> d(num.size());
  rep(i,num.size()) {
    d[i] = from[i].size();
    if(d[i]==0) nxt.pb(i);
  }

  int ans = 0;
  int visited = num.size();
  while(visited > 0) {
    ans++;
    vector<int> tmp;
    if(nxt.size() == 0) {
      cout << -1 << endl;
      return 0;
    }
    for(auto v : nxt) {
      visited--;
      for(auto i : to[v]) {
        d[i]--;
        if(d[i]==0) tmp.pb(i);
      }
    }
    swap(tmp, nxt);
  }

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result