Submission #7314254


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

map<PLL, vector<PLL>> nexts; // edges[v]: {u1, u2, ..}
map<PLL, ll> prevs;
vector<ll> a[2000];

PLL ver(ll i, ll j) {
  if (i > j)
    swap(i, j);
  return PLL(i, j);
}

signed main() {
  ll N;
  cin >> N;
  rep(i,N) {
    rep(j,N-1) {
      ll x;
      cin >> x;
      x--;
      a[i].push_back(x);
    }
  }
  rep(i,N) {
    rep(j,N-2) {
      auto cur = ver(i, a[i][j]);
      auto nex = ver(i, a[i][j+1]);
      nexts[cur].push_back(nex);
      prevs[nex]++;
      // printf("cur: (%d, %d) nex: (%d, %d)\n", cur.first, cur.second, nex.first, nex.second);
    }
  }

  // deleted candinates
  vector<PLL> can;
  rep(i,N) rep(j,i) {
    auto v = ver(i,j);
    if (prevs[v] == 0){
      can.push_back(v);
    }
  }
  //for (auto e : can) {
  //  printf("(%d, %d)\n", e.first, e.second);
  //}

  ll ans = 0;
  ll done = 0;
  while (done < N*(N-1)/2) {
    if (can.size() == 0) {
      cout << -1 << endl;
      return 0;
    }
    vector<PLL> t;
    for (auto v : can) {
      done++;
      for (auto u: nexts[v]) {
        prevs[u]--;
        if (prevs[u] == 0) {
          t.push_back(u);
        }
      }
    }
    can = t;
    ans++;
  }

  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task E - League
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1481 Byte
Status
Exec Time 1990 ms
Memory 111744 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 500 / 500 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
b04 1 ms 256 KB
b05 1 ms 256 KB
b06 1 ms 256 KB
b07 1 ms 256 KB
b08 1733 ms 109696 KB
b09 1165 ms 111744 KB
b10 1989 ms 109696 KB
b11 1990 ms 109568 KB
b12 460 ms 33280 KB
b13 375 ms 26496 KB
b14 137 ms 13312 KB
b15 101 ms 9984 KB
b16 43 ms 6144 KB
b17 30 ms 3584 KB
b18 299 ms 20864 KB
b19 234 ms 17152 KB
b20 48 ms 6528 KB
b21 42 ms 4352 KB
b22 12 ms 2304 KB
b23 5 ms 896 KB