結果

問題 No.1612 I hate Construct a Palindrome
ユーザー tnakao0123tnakao0123
提出日時 2021-07-23 03:31:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,512 bytes
コンパイル時間 1,030 ms
コンパイル使用メモリ 103,168 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-18 00:43:19
合計ジャッジ時間 8,702 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 3 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 3 ms
5,376 KB
testcase_26 AC 3 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 3 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 WA -
testcase_38 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 1612.cc:  No.1612 I hate Construct a Palindrome - yukicoder
 */

#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 = 10000;
const int MAX_M = 20000;

/* typedef */

typedef queue<int> qi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

/* global variables */

vpii nbrs[MAX_N];
char cs[MAX_M];
pii es[MAX_M], ps0[MAX_N], ps1[MAX_N];
int ds0[MAX_N], ds1[MAX_N];
int ts[MAX_N * 2], ts0[MAX_N], ts1[MAX_N];

/* subroutines */

void bfs(int n, int st, int ds[], pii ps[]) {
  fill(ds, ds + n, -1);
  ds[st] = 0;
  ps[st] = pii(-1, -1);

  qi q;
  q.push(st);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    for (auto ve: nbrs[u]) {
      int v = ve.first;
      if (ds[v] < 0) {
	ds[v] = ds[u] + 1;
	ps[v] = pii(u, ve.second);
	q.push(v);
      }
    }
  }
}

int revpath(pii ps[], int gl, int ts[]) {
  int l = 0;
  for (int u = gl; ps[u].second >= 0; u = ps[u].first)
    ts[l++] = ps[u].second;
  return l;
}

bool palindrome(int l, int ts[]) {
  for (int i = 0, j = l - 1; i < j; i++, j--)
    if (cs[ts[i]] != cs[ts[j]]) return false;
  return true;
}

/* main */

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

  for (int i = 0; i < m; i++) {
    int u, v;
    char w[4];
    scanf("%d%d%s", &u, &v, w);
    u--, v--;
    cs[i] = w[0];
    nbrs[u].push_back(pii(v, i));
    nbrs[v].push_back(pii(u, i));
    es[i] = pii(u, v);
  }

  int e0 = nbrs[0][0].second, e1 = -1;
  for (int i = 0; i < m; i++)
    if (i != e0 && cs[e0] != cs[i]) {
      e1 = i;
      break;
    }
  if (e1 < 0) { puts("-1"); return 0; }
  //printf("e0=%d, e1=%d\n", e0, e1);

  bfs(n, nbrs[0][0].first, ds0, ps0);
  bfs(n, n - 1, ds1, ps1);

  int e1u = es[e1].first, e1v = es[e1].second;
  if (ds0[e1u] > ds0[e1v]) swap(e1u, e1v);
  int l0 = revpath(ps0, e1u, ts0);

  int k = 0;
  ts[k++] = e0;
  for (int i = l0 - 1; i >= 0; i--) ts[k++] = ts0[i];
  ts[k++] = e1;

  if (ds1[e1v] > ds1[e1u]) swap(e1v, e1u), ts[k++] = e1;
  int l1 = revpath(ps1, e1v, ts1);
  for (int i = 0; i < l1; i++) ts[k++] = ts1[i];

  if (palindrome(k, ts)) ts[k + 2] = ts[k + 1] = ts[k], k += 2;

  printf("%d\n", k);
  for (int i = 0; i < k; i++) printf("%d\n", ts[i] + 1);
  return 0;
}
0