結果

問題 No.3040 Aoiスコア
ユーザー Leal-0
提出日時 2025-02-28 22:46:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,609 bytes
コンパイル時間 3,688 ms
コンパイル使用メモリ 293,248 KB
実行使用メモリ 11,300 KB
最終ジャッジ日時 2025-06-20 20:59:47
合計ジャッジ時間 6,882 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__


int main(){
    ll n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    vector<vector<ll>> deps(n,vector<ll>(0));
    ll quesct=0;
    rep(i,n) {
        if(s[i]=='?') quesct++;
    }
    //cout<<quesct<<endl;
    rep(i,m) {
        ll a,b;
        cin>>a>>b;
        a--;b--;
        deps[a].push_back(b);
        deps[b].push_back(a);
    }
    ll ans=0;
    rep(i,n) {
        vector<char> c(3);
        dfs(ans,deps,s,0,c,i,-1,quesct);
    }
    cout<<ans<<endl;
}

#else
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,l,r) for(int i=l;i<=r;i++)
using ll = long long;
#define mod 998244353ll
#define vout(v) for(auto i :v) cout<<i<<" ";
#define INF 922330000000000000ll
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define enld endl
#define Rn return
#define vl vector<ll>

ll quesct=0;
ll modpow(ll base, ll exp, ll mode) {
    ll result=1;
    if(mode==0) {
        rep(i,exp) result*=base;
    } else { //繰り返しsquare
        base%=mod;
        while(exp>0) {
            if(exp&1)
                result=(result*base)%mod;
            base=(base*base)%mod;
            exp>>=1;
        }
    }
    return result;
}


ll gcd(ll a,ll b) {  //Euclid
    if(a<b) return gcd(b,a);
    if(a%b==0) return b;
    return gcd(b,a%b);
}


void dfs(ll& ans,vector<vector<ll>>&g,string& s,ll step,vector<char>& c,ll cur,ll prev,ll &quesct) {
    c[step]=s[cur];
    if(step==2) {
        ll qt=0;
        if(c[0]=='?') qt++;
        if(c[1]=='?') qt++;
        if(c[2]=='?') qt++;
        if((c[0]!='a' && c[0]!='?') || (c[1]!='o' && c[1]!='?') || (c[2]!='i' && c[2]!='?')) return;
        ans+=modpow(26,quesct-qt,1);
        ans%=mod;
        return;
    }
    for(auto nx:g[cur]) {
        if(nx==prev) continue;
        dfs(ans,g,s,step+1,c,nx,cur,quesct);
    }
}


ll lensum(ll l,ll r) {
    ll len=r-l+1;
    return (l-1)*len + (r-l+1)*(r-l+1)/2;
}
vector<ll> Erasieve(ll n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false; 

    for (int i=2;i*i<=n;++i) {
        if (is_prime[i]) {
            for (int j=i*i;j<=n;j+=i) is_prime[j] = false;
        }
    }
    vector<ll> primes;
    srep(i,2,n) {
        if (is_prime[i]) primes.push_back(i);
    }

    return primes;
}

ll divcount(ll n) {
    ll ans=0;
    for(int i=1;i*i<=n;i++) {
        if(n%i==0) ans+=(i*i==n ? 1:2);
    }
    return ans;
}
struct UnionFind {
    vector<int> par;  
    vector<int> rank;
    UnionFind(int N) : par(N), rank(N, 0) {
        for (int i = 0; i < N; i++) {
            par[i] = i;
        }
    }
    // 経路圧縮
    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return; 
        if (rank[rx] < rank[ry]) {
            par[rx] = ry;
        } else {
            par[ry] = rx;
            if (rank[rx] == rank[ry]) {
                rank[rx]++;
            }
        }
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }
};



template <class T> void vecpr(T first,T last) {
    ll tmp=0;
    for(auto it=first;it!=last;++it) {
        if(tmp) cout<<" ";
        cout<<*it;
        tmp++;
    }
    cout<<endl;
}

template <class T> void vvpr(vector<vector<T>> a) {
    for(int i=0;i<(ll)a.size();i++) {
        for(int j=0;j<(ll)a[i].size();j++) {
            if(j) cout<<" ";
            cout<<a[i][j];
        }
        cout<<endl;
    }
}

vector<ll> slmax(vector<ll> a, ll limit, ll breadth) {//slidewindowによる幅breadthでの区間最大値評価,limit=a.size()
    deque<ll> deq;
    vector<ll> max_numbers(limit, (-1)*INF);
    rep(i, limit) {
        while (!deq.empty() && deq.front() <= i - breadth) deq.pop_front();
        while (!deq.empty() && a[deq.back()] <= a[i]) deq.pop_back();
        deq.push_back(i);
        max_numbers[i] = a[deq.front()];
    }
    return max_numbers;
}

vector<ll> slmin(vector<ll> a, ll limit, ll breadth) {//slidewindowによる幅breadthでの区間最小値評価,limit=a.size()
    deque<ll> deq;
    vector<ll> min_numbers(limit, INF);
    rep(i, limit) {
        while (!deq.empty() && deq.front() <= i - breadth) deq.pop_front();
        while (!deq.empty() && a[deq.back()] >= a[i]) deq.pop_back();
        deq.push_back(i);
        min_numbers[i] = a[deq.front()];
    }
    return min_numbers;
}


vector<ll> lis_min(vector<ll> &a) { //最後まで見たときに、「長さiの最後尾は最小でいくつか？」を返す
    ll n=(ll)a.size();
    vector<ll> dp(n,INF);
    rep(i,n){
    auto itr = lower_bound(dp.begin(),dp.end(), a[i]);
    *itr = a[i]; 
    }
    return dp;
}//あんま使えない

void lis_min_update(vector<ll>& dp, ll x) { //↑を一回ごとに処理するやつ (cf.abc393-f);
    auto it=lower_bound(dp.begin(), dp.end(), x);
    if(it==dp.end())
        dp.push_back(x);
    else 
        *it=x;
}




vector<ll> lis_size(vector<ll>& a ,vector<ll>&seqcopy) { // 最長増加部分列の a index目までみた時点の長さがdp[i]
    ll n=a.size();
    vector<ll> dp(n,1);  
    vector<ll> seq;       

   rep(i,n) {
        auto it=lower_bound(seq.begin(), seq.end(), a[i]);
        
        if (it==seq.end())  seq.push_back(a[i]);
        else *it=a[i];
        dp[i]=distance(seq.begin(), lower_bound(seq.begin(), seq.end(), a[i]))+1;
    }
    srep(i,1,n-1) {
        if(dp[i]<dp[i-1]) dp[i]=dp[i-1];
    }
    seqcopy=seq;
    return dp;
}



#endif
0