結果

問題 No.895 MESE
ユーザー tnakao0123tnakao0123
提出日時 2019-09-29 21:07:20
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,952 bytes
コンパイル時間 659 ms
コンパイル使用メモリ 92,700 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-03 04:36:58
合計ジャッジ時間 3,298 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 RE -
testcase_11 RE -
testcase_12 WA -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

/*  -*- 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