#1198393 (C++23(gcc16)) No.3561 Collect KCPC

• 問題: No.3561 Collect KCPC
• ユーザー: C
• 提出日時: 2026-11-12 14:40:28
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 74 ms / 6,000 ms
• コード長: 4,752 bytes
• コンパイル時間: 7,959 ms
• コンパイル使用メモリ: 604,200 KB
• 実行使用メモリ: 29,364 KB
• 最終ジャッジ日時: 2026-11-12 14:40:49
• 合計ジャッジ時間: 16,125 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge3_0

サブタスク	配点	結果
部分点1	10 %	AC * 15
部分点2	20 %	AC * 15
部分点3	20 %	AC * 13
部分点4	50 %	AC * 51
合計	100 点

ソースコード

#include <bits/stdc++.h>
#include <immintrin.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
using vvm=vector<vm>;

#line 2 "graph/static-graph.hpp"

namespace StaticGraphImpl {

template <typename T, bool Cond = is_void<T>::value>
struct E;
template <typename T>
struct E<T, false> {
  int to;
  T cost;
  E() {}
  E(const int& v, const T& c) : to(v), cost(c) {}
  operator int() const { return to; }
};
template <typename T>
struct E<T, true> {
  int to;
  E() {}
  E(const int& v) : to(v) {}
  operator int() const { return to; }
};

template <typename T = void>
struct StaticGraph {
 private:
  template <typename It>
  struct Es {
    It b, e;
    It begin() const { return b; }
    It end() const { return e; }
    int size() const { return int(e - b); }
    auto&& operator[](int i) const { return b[i]; }
  };
  
  int N, M, ec;
  vector<int> head;
  vector<pair<int, E<T>>> buf;
  vector<E<T>> es;

  void build() {
    partial_sum(begin(head), end(head), begin(head));
    es.resize(M);
    for (auto&& [u, e] : buf) es[--head[u]] = e;
  }

 public:
  StaticGraph(int _n, int _m) : N(_n), M(_m), ec(0), head(N + 1, 0) {
    buf.reserve(M);
  }

  template <typename... Args>
  void add_edge(int u, Args&&... args) {
#pragma GCC diagnostic ignored "-Wnarrowing"
    buf.emplace_back(u, E<T>{std::forward<Args>(args)...});
#pragma GCC diagnostic warning "-Wnarrowing"
    ++head[u];
    if ((int)buf.size() == M) build();
  }

  Es<typename vector<E<T>>::iterator> operator[](int u) {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  const Es<typename vector<E<T>>::const_iterator> operator[](int u) const {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  int size() const { return N; }
};

}  // namespace StaticGraphImpl

using StaticGraphImpl::StaticGraph;

/**
 * @brief Static Graph
 * @docs docs/graph/static-graph.md
 */


#line 2 "data-structure/radix-heap.hpp"

template <typename Key, typename Val>
struct RadixHeap {
  using uint = typename make_unsigned<Key>::type;
  static constexpr int bit = sizeof(Key) * 8;
  array<vector<pair<uint, Val> >, bit + 1> vs;
  array<uint, bit + 1> ms;

  int s;
  uint last;

  RadixHeap() : s(0), last(0) { fill(begin(ms), end(ms), uint(-1)); }

  bool empty() const { return s == 0; }

  int size() const { return s; }

  __attribute__((target("lzcnt"))) inline uint64_t getbit(uint a) const {
    return 64 - _lzcnt_u64(a);
  }

  void push(const uint &key, const Val &val) {
    s++;
    uint64_t b = getbit(key ^ last);
    vs[b].emplace_back(key, val);
    ms[b] = min(key, ms[b]);
  }

  pair<uint, Val> pop() {
    if (ms[0] == uint(-1)) {
      int idx = 1;
      while (ms[idx] == uint(-1)) idx++;
      last = ms[idx];
      for (auto &p : vs[idx]) {
        uint64_t b = getbit(p.first ^ last);
        vs[b].emplace_back(p);
        ms[b] = min(p.first, ms[b]);
      }
      vs[idx].clear();
      ms[idx] = uint(-1);
    }
    --s;
    auto res = vs[0].back();
    vs[0].pop_back();
    if (vs[0].empty()) ms[0] = uint(-1);
    return res;
  }
};

/**
 * @brief Radix Heap
 * @docs docs/data-structure/radix-heap.md
 */

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	StaticGraph<int>g(N,M);
	rep(i,0,M){
		int U,V,C;
		cin>>U>>V>>C;
		g.add_edge(V-1,U-1,C);
	}
	string S;
	cin>>S;
	RadixHeap<ll,pi>q;
	rep(b,0,N){
		if(S[b]=='C')q.push(0,{b,b});
	}
	vector<pi>labels(2*N,{-1,-1});
	vector<char>done(2*N);
	while(!q.empty()){
		auto [d,p]=q.pop();
		auto& [state,b]=p;
		int j=state/N;
		int v=state%N;
		if(j<2){
			auto&[b0,b1]=labels[state];
			if(b==b0||b==b1)continue;
			if(b0==-1)b0=b;
			else if(b1==-1)b1=b;
			else continue;
		}else{
			if(done[state-2*N])continue;
			done[state-2*N]=true;
		}
		if(j==3&&v==0){
			cout<<d<<'\n';
			return 0;
		}
		if(j==0&&S[v]=='P')q.push(d,{N+v,b});
		else if(j==1&&S[v]=='C'&&v!=b)q.push(d,{2*N+v,-1});
		else if(j==2&&S[v]=='K')q.push(d,{3*N+v,-1});
		for(auto&[u,c]:g[v])q.push(d+c,{j*N+u,b});
	}
	cout<<-1<<'\n';
}