結果

問題 No.895 MESE
コンテスト
ユーザー tnakao0123
提出日時 2019-09-29 21:07:20
言語 C++11（廃止可能性あり）
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,952 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 659 ms
コンパイル使用メモリ 92,700 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-03 04:36:58
合計ジャッジ時間 3,298 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 8 RE * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:65:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   65 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:69:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |     scanf("%d%d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

/*  -*- coding: utf-8 -*-
 *
 * f.cc: F - Pure
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 1000;
const int BN = 10;
const int INF = 1 << 30;

/* typedef */

typedef vector<int> vi;
typedef queue<int> qi;

/* global variables */

vi nbrs[MAX_N];
int ds[MAX_N], prts[MAX_N][BN], vn, vs[MAX_N];
bool used[MAX_N];

/* subroutines */

int find_lca(int u, int v) {
  if (ds[u] > ds[v]) swap(u, v);

  for (int i = BN - 1; i >= 0; i--)
    if (((ds[v] - ds[u]) >> i) & 1) v = prts[v][i];
  if (u == v) return u;

  for(int i = BN - 1; i >= 0; i--)
    if (prts[u][i] != prts[v][i]) {
      u = prts[u][i];
      v = prts[v][i];
    }
  return prts[u][0];
}

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    nbrs[a].push_back(b);
  }

  memset(ds, -1, sizeof(ds));
  int mink = INF, minu = -1, minv = -1;

  for (int st = 0; st < n; st++)
    if (ds[st] < 0) {
      ds[st] = 0;
      prts[st][0] = -1;

      qi q;
      q.push(st);
  
      while (! q.empty()) {
	int u = q.front(); q.pop();
	int up = prts[u][0], ud = ds[u], vd = ud + 1;

	for (int b = 0; b < BN - 1; b++)
	  prts[u][b + 1] = (prts[u][b] >= 0) ? prts[prts[u][b]][b] : -1;

	vi &nbru = nbrs[u];
	for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
	  int &v = *vit;
	  if (v != up) {
	    if (ds[v] < 0) {
	      ds[v] = vd;
	      prts[v][0] = u;
	      q.push(v);
	    }
	    else if (find_lca(u, v) == v) {
	      int k = ds[u] - ds[v] + 1;
	      if (mink > k)
		mink = k, minu = u, minv = v;
	    }
	  }
	}
      }
    }
  //printf("mink = %d, minu = %d, minv = %d\n", mink, minu, minv);

  if (mink >= INF) {
    puts("-1");
    return 0;
  }

  vn = mink;
  for (int i = vn - 1, u = minu; i >= 0; i--, u = prts[u][0])
    vs[i] = u, used[u] = true;

  for (;;) {
    int su = -1, sv = -1;
    for (int i = 0; i < vn; i++) {
      int u0 = vs[i], u1 = vs[(i + 1) % vn], u2 = vs[(i + vn - 1) % vn];
      vi &nbru = nbrs[u0];
      for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
	int &v = *vit;
	if (v != u1 && v != u2 && used[v]) {
	  su = u0, sv = v;
	  break;
	}
      }
      if (su >= 0) break;
    }
    if (su < 0) break;

    int vm = 0;
    memset(used, false, sizeof(used));
    for (int i = 0, ok = 1; i < vn; i++) {
      if (ok) {
	vs[vm++] = vs[i];
	used[vs[i]] = true;
	if (vs[i] == su) ok = false;
      }
      else if (vs[i] == sv) {
	vs[vm++] = vs[i];
	used[vs[i]] = true;
      }
    }
    vn = vm;
  }
  
  printf("%d\n", vn);
  for (int i = 0; i < vn; i++) printf("%d\n", vs[i] + 1);

  return 0;
}
0