結果

問題 No.1612 I hate Construct a Palindrome
ユーザー tnakao0123tnakao0123
提出日時 2021-07-23 03:39:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 2,514 bytes
コンパイル時間 970 ms
コンパイル使用メモリ 99,060 KB
実行使用メモリ 16,544 KB
最終ジャッジ日時 2023-09-25 00:35:32
合計ジャッジ時間 4,719 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,596 KB
testcase_01 AC 4 ms
9,592 KB
testcase_02 AC 75 ms
14,688 KB
testcase_03 AC 4 ms
9,588 KB
testcase_04 AC 4 ms
9,636 KB
testcase_05 AC 73 ms
14,744 KB
testcase_06 AC 62 ms
13,916 KB
testcase_07 AC 62 ms
13,896 KB
testcase_08 AC 60 ms
13,812 KB
testcase_09 AC 62 ms
13,744 KB
testcase_10 AC 59 ms
13,820 KB
testcase_11 AC 58 ms
13,796 KB
testcase_12 AC 68 ms
13,956 KB
testcase_13 AC 67 ms
13,944 KB
testcase_14 AC 66 ms
13,900 KB
testcase_15 AC 103 ms
16,412 KB
testcase_16 AC 100 ms
16,544 KB
testcase_17 AC 108 ms
16,476 KB
testcase_18 AC 4 ms
9,524 KB
testcase_19 AC 4 ms
9,620 KB
testcase_20 AC 4 ms
9,524 KB
testcase_21 AC 4 ms
9,624 KB
testcase_22 AC 5 ms
9,528 KB
testcase_23 AC 4 ms
9,588 KB
testcase_24 AC 4 ms
9,680 KB
testcase_25 AC 5 ms
9,548 KB
testcase_26 AC 5 ms
9,592 KB
testcase_27 AC 4 ms
9,532 KB
testcase_28 AC 5 ms
9,592 KB
testcase_29 AC 5 ms
9,452 KB
testcase_30 AC 4 ms
9,452 KB
testcase_31 AC 4 ms
9,560 KB
testcase_32 AC 4 ms
9,488 KB
testcase_33 AC 4 ms
9,520 KB
testcase_34 AC 4 ms
9,484 KB
testcase_35 AC 4 ms
9,544 KB
testcase_36 AC 4 ms
9,568 KB
testcase_37 AC 4 ms
9,556 KB
testcase_38 AC 4 ms
9,468 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 = 100000;
const int MAX_M = 200000;

/* 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 + 1] = ts[k] = ts[k - 1], k += 2;

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