結果

問題 No.1612 I hate Construct a Palindrome
ユーザー chocoruskchocorusk
提出日時 2021-07-21 22:44:27
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 353 ms / 2,000 ms
コード長 3,390 bytes
コンパイル時間 3,353 ms
コンパイル使用メモリ 194,088 KB
実行使用メモリ 14,456 KB
最終ジャッジ日時 2023-09-24 19:00:49
合計ジャッジ時間 8,117 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,904 KB
testcase_01 AC 6 ms
5,896 KB
testcase_02 AC 353 ms
12,364 KB
testcase_03 AC 2 ms
5,860 KB
testcase_04 AC 5 ms
5,832 KB
testcase_05 AC 352 ms
12,428 KB
testcase_06 AC 138 ms
11,016 KB
testcase_07 AC 148 ms
11,340 KB
testcase_08 AC 124 ms
10,868 KB
testcase_09 AC 94 ms
10,800 KB
testcase_10 AC 89 ms
10,784 KB
testcase_11 AC 89 ms
10,888 KB
testcase_12 AC 104 ms
11,076 KB
testcase_13 AC 101 ms
11,052 KB
testcase_14 AC 102 ms
11,200 KB
testcase_15 AC 176 ms
14,456 KB
testcase_16 AC 183 ms
14,264 KB
testcase_17 AC 182 ms
14,284 KB
testcase_18 AC 3 ms
5,912 KB
testcase_19 AC 3 ms
5,780 KB
testcase_20 AC 3 ms
5,784 KB
testcase_21 AC 3 ms
5,884 KB
testcase_22 AC 4 ms
5,852 KB
testcase_23 AC 3 ms
6,012 KB
testcase_24 AC 3 ms
5,844 KB
testcase_25 AC 4 ms
5,820 KB
testcase_26 AC 4 ms
5,812 KB
testcase_27 AC 3 ms
5,828 KB
testcase_28 AC 2 ms
6,016 KB
testcase_29 AC 3 ms
5,784 KB
testcase_30 AC 2 ms
5,760 KB
testcase_31 AC 3 ms
5,796 KB
testcase_32 AC 3 ms
5,732 KB
testcase_33 AC 2 ms
5,956 KB
testcase_34 AC 3 ms
5,736 KB
testcase_35 AC 3 ms
5,972 KB
testcase_36 AC 2 ms
5,852 KB
testcase_37 AC 2 ms
5,832 KB
testcase_38 AC 3 ms
5,772 KB
権限があれば一括ダウンロードができます

ソースコード

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