結果

問題 No.1612 I hate Construct a Palindrome
コンテスト
ユーザー tnakao0123
提出日時 2021-07-23 03:31:22
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 WA * 3 RE * 14
権限があれば一括ダウンロードができます

ソースコード

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