結果

問題 No.1612 I hate Construct a Palindrome
コンテスト
ユーザー msm1993
提出日時 2021-08-02 09:48:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 350 ms / 2,000 ms
コード長 3,390 bytes
コンパイル時間 3,722 ms
コンパイル使用メモリ 179,804 KB
実行使用メモリ 14,404 KB
最終ジャッジ日時 2024-09-16 13:06:52
合計ジャッジ時間 8,292 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
int n, m;
vector<P> g[100010];
char c[200020];
int a[200020], b[200020];
int main()
{
    cin>>n>>m;
    
    for(int i=0; i<m; i++){
        cin>>a[i]>>b[i]>>c[i];
        a[i]--; b[i]--;
        g[a[i]].push_back({b[i],i});
        g[b[i]].push_back({a[i],i});
    }
    auto e0=g[0][0];
    int k=0;
    for(;k<m; k++){
        if(c[e0.second]!=c[k]) break;
    }
    if(k==m){
        cout<<-1<<endl;
        return 0;
    }
    auto calc=[&](int s, int t)->vector<int>{
        int d[100010];
        fill(d, d+n, n+1);
        queue<int> que; que.push(s);
        d[s]=0;
        while(!que.empty()){
            int x=que.front(); que.pop();
            for(auto q:g[x]){
                int y=q.first;
                if(d[y]>d[x]+1){
                    d[y]=d[x]+1;
                    que.push(y);
                }
            }
        }
        vector<int> res;
        while(s!=t){
            for(auto q:g[t]){
                if(d[t]-1==d[q.first]){
                    res.push_back(q.second);
                    t=q.first;
                    break;
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    };
    int s=e0.first;
    auto sa=calc(s, a[k]), sb=calc(s, b[k]);
    auto bt=calc(b[k], n-1), at=calc(a[k], n-1);
    if(sa.size()+bt.size()>sb.size()+at.size()){
        swap(sa, sb), swap(bt, at);
    }
    vector<int> ans{e0.second};
    for(auto i:sa) ans.push_back(i);
    ans.push_back(k);
    for(auto i:bt) ans.push_back(i);
    for(int l=0; ; l++){
        bool ok=0;
        int K=ans.size();
        for(int i=0; i<K; i++){
            if(c[ans[i]]!=c[ans[K-1-i]]){
                ok=1;break;
            }
        }
        if(ok){
            cout<<K<<endl;
            for(auto i:ans){
                cout<<i+1<<endl;
            }
            return 0;
        }
        ans.insert(ans.begin(), e0.second);
        ans.insert(ans.begin(), e0.second);
    }

    // map<char, int> mp1, mpn;
    // for(auto e1:g[0]) mp1[c[e1.second]]=e1.second;
    // for(auto e1:g[n-1]) mpn[c[e1.second]]=e1.second;
    // for(auto p:mp1) for(auto q:mpn){
    //     if(p.first!=q.first){
    //         vector<int> ans;
    //         ans.push_back(p.second);
    //         int d[100010];
    //         fill(d, d+n, n+1);
    //         int s, t;
    //         if(a[p.second]==0){
    //             s=b[p.second];
    //         }else{
    //             s=a[p.second];
    //         }
    //         if(a[q.second]==n-1){
    //             t=b[p.second];
    //         }else{
    //             t=a[p.second];
    //         }
    //         d[s]=0;
    //         queue<int> que;
    //         que.push(s);
    //         while(!que.empty()){

    //         }
    //     }
    // }
    return 0;
}
0