結果
| 問題 | No.2780 The Bottle Imp |
| ユーザー |
 mamenta
|
| 提出日時 | 2024-06-07 22:37:29 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 24,683 bytes |
| コンパイル時間 | 2,797 ms |
| コンパイル使用メモリ | 209,452 KB |
| 実行使用メモリ | 32,128 KB |
| 最終ジャッジ日時 | 2024-06-08 10:35:12 |
| 合計ジャッジ時間 | 4,518 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 7 ms
19,712 KB |
| testcase_01 | AC | 7 ms
19,712 KB |
| testcase_02 | AC | 7 ms
19,780 KB |
| testcase_03 | AC | 7 ms
19,712 KB |
| testcase_04 | AC | 7 ms
19,840 KB |
| testcase_05 | AC | 7 ms
19,712 KB |
| testcase_06 | AC | 7 ms
19,840 KB |
| testcase_07 | AC | 22 ms
22,528 KB |
| testcase_08 | AC | 25 ms
22,784 KB |
| testcase_09 | AC | 25 ms
22,912 KB |
| testcase_10 | AC | 26 ms
22,912 KB |
| testcase_11 | AC | 21 ms
22,528 KB |
| testcase_12 | AC | 29 ms
24,832 KB |
| testcase_13 | AC | 31 ms
24,832 KB |
| testcase_14 | AC | 20 ms
21,888 KB |
| testcase_15 | AC | 20 ms
21,760 KB |
| testcase_16 | AC | 21 ms
21,704 KB |
| testcase_17 | AC | 20 ms
21,756 KB |
| testcase_18 | AC | 21 ms
21,760 KB |
| testcase_19 | AC | 20 ms
21,700 KB |
| testcase_20 | AC | 20 ms
21,632 KB |
| testcase_21 | AC | 20 ms
21,760 KB |
| testcase_22 | AC | 15 ms
21,060 KB |
| testcase_23 | AC | 19 ms
21,504 KB |
| testcase_24 | AC | 22 ms
22,400 KB |
| testcase_25 | AC | 30 ms
23,680 KB |
| testcase_26 | AC | 19 ms
21,760 KB |
| testcase_27 | AC | 19 ms
22,300 KB |
| testcase_28 | AC | 19 ms
22,272 KB |
| testcase_29 | WA | - |
| testcase_30 | AC | 16 ms
22,084 KB |
| testcase_31 | AC | 28 ms
25,216 KB |
| testcase_32 | AC | 14 ms
20,804 KB |
| testcase_33 | AC | 36 ms
32,128 KB |
| testcase_34 | AC | 36 ms
32,064 KB |
| testcase_35 | AC | 13 ms
20,480 KB |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | AC | 13 ms
20,480 KB |
| testcase_39 | AC | 27 ms
26,112 KB |
| testcase_40 | AC | 28 ms
26,172 KB |
| testcase_41 | WA | - |
| testcase_42 | AC | 7 ms
19,712 KB |
| testcase_43 | AC | 7 ms
19,840 KB |
ソースコード
#include<iostream>
#include<functional>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<cstring>
#include<bitset>
#include<iomanip>
#include<random>
#include<fstream>
#include<complex>
#include<time.h>
#include<stack>
#include<cassert>
using namespace std;
#define endl "\n"
#define ll long long
#define ch char
#define vec vector
#define vll vector<ll>
#define sll set<ll>
#define pll pair<ll,ll>
#define mkp make_pair
#define mll map<ll,ll>
#define puf push_front
#define pub push_back
#define pof pop_front()
#define pob pop_back()
#define em empty()
#define fi first
#define se second
#define fr front()
#define ba back()
#define be begin()
#define rbe rbegin()
#define en end()
#define ren rend()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define fo(i,x,y) for(ll i=x;i<=y;++i)
#define fa(i,v) for(auto &i:v)
#define re return
#define sz size()
#define so(v) sort(all(v))
#define pop_count(x) __builtin_popcount(x)
#define rso(v) sort(rall(v))
#define rev(v) reverse(all(v))
#define i(x) for(ll i=0;i<x;++i)
#define j(x) for(ll j=0;j<x;++j)
#define k(x) for(ll k=0;k<x;++k)
#define xx(k) while(k--)
#define wh(x) while(x)
#define st string
//10^x 8765432109876543210
#define MAX 8611686018427387000
#define zeros(x) __builtin_ctzll(x)
#define in insert
#define uniq(v) v.erase(unique(all(v)),v.en);
#define er(i,n) erase(i,n);
//#define co(x,a) count(all(x),a)
#define lo(v,a) lower_bound(v.begin(),v.end(),a)
#define dou double
#define ge(x,...) x __VA_ARGS__; ci(__VA_ARGS__);
#define fix(n,ans) cout<<fixed<<std::setprecision(n)<<ans<<endl;
void cc(){ cout<<endl; };
void ff(){ cout<<endl; };
void cl(){ cout<<endl; };
template<class T,class... A> void ff(T a,A... b){ cout<<a; (cout<<...<<(cout<<' ',b)); cout<<endl; };
template<class T,class... A> void cc(T a,A... b){ cout<<a; (cout<<...<<(cout<<' ',b)); cout<<' '; };
template<class T,class... A> void cl(T a,A... b){ cout<<a; (cout<<...<<(cout<<'\n',b)); cout<<endl; };
template<class T,class... A> void cn(T a,A... b){ cout<<a; (cout<<...<<(cout<<"",b)); };
template<class... A> void ci(A&... a){ (cin>>...>>a); };
template<class T>void ou(T v){fa(i,v)cout<<i<<" ";cout<<endl;}
template<class T>void oun(T v){fa(i,v)cout<<i;cout<<endl;}
template<class T>void ouu(T v){fa(i,v){fa(j,i)cout<<j<<" ";cout<<endl;}}
template<class T> void oul(T v){fa(i,v)cout<<i<<endl;}
template<class T>void in(T &v){fa(i,v)cin>>i;}
template<class T>void inn(T &v){fa(i,v)fa(j,i)cin>>j;}
template<class T>void oump(T &v){fa(i,v)ff(i.fi,i.se);}
template<class T,class A>void pi(pair<T,A> &p){ci(p.fi,p.se);}
template<class T,class A>void po(pair<T,A> &p){ff(p.fi,p.se);}
template<class T,class... A> void fl(T a,A... b){ cout<<a; (cout<<...<<(cout<<' ',b)); cout<<endl<<flush; };
ll mod = 1000000007;
ll mod9= 998244353;
void init();
void solve();
/*
void ori();
ll random_(){
std::random_device seed_gen;
std::mt19937 engine(seed_gen());
// [-1.0, 1.0)の値の範囲で、等確率に実数を生成する
std::uniform_real_distribution<> dist1(1.0, 100000);
i(10000){ // 各分布法に基いて乱数を生成
ll n = dist1(engine);
} return 0;
}
*/
mll to_prime(ll x){
mll mp;
for(ll i=2;i*i<=x;++i){
while(x%i==0){
++mp[i];
x/=i;
}
}
if(x!=1)
++mp[x];
re mp;
}
#define acc(v) accumulate(v.begin(),v.end(),0LL)
#define acci(v,i) accumulate(v.begin(),v.begin()+i,0LL)
#define dll deque<ll>
int main(void){
init();
solve();
return 0;
}
template <typename T>class pnt{
public:
T x,y;
pnt(T x=0,T y=0):x(x),y(y){}
pnt operator + (const pnt r)const {
return pnt(x+r.x,y+r.y);}
pnt operator - (const pnt r)const {
return pnt(x-r.x,y-r.y);}
pnt operator * (const pnt r)const {
return pnt(x*r.x,y*r.y);}
pnt operator / (const pnt r)const {
return pnt(x/r.x,y/r.y);}
pnt &operator += (const pnt r){
x+=r.x;y+=r.y;return *this;}
pnt &operator -= (const pnt r){
x-=r.x;y-=r.y;return *this;}
pnt &operator *= (const pnt r){
x*=r.x;y*=r.y;return *this;}
pnt &operator /= (const pnt r){
x/=r.x;y/=r.y;return *this;}
ll dist(const pnt r){
re (x-r.x)*(x-r.x)+(y-r.y)*(y-r.y);
}
ll man(const pnt r){
re abs(x-r.x)+abs(y-r.y);
}
pnt rot(const dou theta){
T xx,yy;
xx=cos(theta)*x-sin(theta)*y;
yy=sin(theta)*x+cos(theta)*y;
return pnt(xx,yy);
}
};
istream &operator >> (istream &is,pnt<dou> &r){is>>r.x>>r.y;return is;}
ostream &operator << (ostream &os,pnt<dou> &r){os<<r.x<<" "<<r.y;return os;}
struct BIT{
ll n;vll v;
BIT(ll n):n(n+n%2),v(2*(n+n%2)){};
ll op(ll x,ll y){
re gcd(x,y);
}
ll sum(ll i){
ll s=0;
while(i){
s=gcd(s,v[i]);
i-=i&-i;
}
re s;
}
void add(ll i,ll x){
while(i<=n){
v[i]=op(v[i],x);
i+=i&-i;
}
}
ll ran(ll l,ll r){
re op(sum(--l),sum(r));
}
};
template<class T>bool chmaxeq(T& a, const T& b) { if (a <= b) { a = b; return 1; } return 0; }
template<class T>bool chmineq(T& a, const T& b) { if (b <= a) { a = b; return 1; } return 0; }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
struct Trie{
struct Node{
vll nxt;
vec<st> done;
ll dep,cnt=0;
Node(ll c_):nxt(30),dep(c_){}
};
ll root=0;
vec<Node>tree={Node(root)};
void ins(st s){
ll c=0;
for(ll i=0;i<s.sz;++i){
ll to=tree[c].nxt[s[i]-'a'];
if(to==0){
to=tree.sz;
tree[c].nxt[s[i]-'a']=to;
tree.pub(Node(i+1));
}
++tree[to].cnt;
c=to;
}
tree[c].done.pub(s);
}
ll cal(st s){
ll ans=0,c=0;
for(ll i=0;i<s.sz;++i){
ll to=tree[c].nxt[s[i]-'a'];
if(tree[to].cnt>1)++ans;
else break;
c=to;
}
re ans;
}
};
#define fo(i,x,y) for(ll i=x;i<=y;++i)
#define rfo(_ii,_xx,_yy) for(ll _ii=_xx;_ii>=_yy;--_ii)
#define qll queue<ll>
template<typename T> using pq= priority_queue<T>;
template<typename T> using pqg= priority_queue<T,vec<T>,greater<T>>;
vec<pair<ch,ll>>rle(st s){//run_length_encoding
ll n=s.sz;
vec<pair<ch,ll>>ans;
for(ll i=0;i<n;++i){
ll cnt=1;
wh(i+1<n&&s[i+1]==s[i]){
++cnt;++i;
}
ans.pub(mkp(s[i],cnt));
}
re ans;
}
vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {
// 行列乗算
int n = a.size();
vector<vector<ll>> res(n, vector<ll>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
res[i][j] += a[i][k] * b[k][j];
res[i][j] %= mod;
}
}
}
return res;
}
vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {
// 行列累乗
int n = a.size();
vector<vector<ll>> res(n, vector<ll>(n));
for (int i = 0; i < n; i++) res[i][i] = 1;
while (b) {
if (b & 1) res = mat_mul(res, a, mod);
a = mat_mul(a, a, mod);
b >>= 1;
}
return res;
}
void Yes(bool f){
ff(f?"Yes":"No");re;
}
void yes(bool f){
ff(f?"yes":"no");re;
}
void YES(bool f){
ff(f?"YES":"NO");re;
}
void sub();
template <class T>
struct Edge {
int rv, from, to; // rev:逆向きの辺の番号
T cap, original_cap;
Edge(int f, int t, T c,int r ) : rv(r), from(f), to(t), cap(c), original_cap(c) {}
};
struct UF{ vll par,rk,siz; UF(ll n):par(n+5,-1),rk(n+5,0){ }
ll root(ll x){ if(par[x]<0)return x; else return par[x]=root(par[x]); }
bool same(ll x,ll y){ return root(x)==root(y); }
bool unite(ll x,ll y){
ll rx=root(x),ry=root(y);
if(rx==ry) return 0;
if(rk[rx]<rk[ry]) swap(rx,ry);
par[rx]+=par[ry]; par[ry]=rx;
if(rk[rx]==rk[ry]) rk[rx]++; return 1;
}
ll size(ll x){ return -par[root(x)]; }
};
ll dijkstra(ll start,ll n){//O((n+m)log(n))
vec<vec<pll>>e(n);
vll dis(n+50,MAX);
pqg<pll>q;q.push({0ll,start});
dis[start]=0;
while(q.em^1){
auto [d,now]=q.top();q.pop();
if(dis[now]<d)continue;
if(now==n)re dis[now];
for(auto[to,cst]:e[now])if(chmin(dis[to],cst+d)){
q.push({dis[to],to});
}
}
re -1;
}
struct UF_norank{ vll par,siz; UF_norank(ll n):par(n+5,-1){ }
ll root(ll x){ if(par[x]<0)return x; else return par[x]=root(par[x]); }
bool same(ll x,ll y){ return root(x)==root(y); }
bool unite(ll from,ll to){
ll r_fr=root(from),r_to=root(to);
if(r_fr==r_to) return 0;
par[r_to]+=par[r_fr]; par[r_fr]=r_to;
return 1;
}
ll size(ll x){ return -par[root(x)]; }
};
vll di(ll start,ll n,vec<vec<pll>>cost){//O((n+m)log(n))
vll dis(n+5,MAX);
pqg<pll>q;q.push({0ll,start});
dis[start]=0;
while(q.em^1){
auto [d,now]=q.top();q.pop();
if(dis[now]<d)continue;
//if(now==goal)break;
for(auto [to,cst]:cost[now]){
if(chmin(dis[to],cst+d)){
q.push({dis[to],to});
}
}
}
re dis;
}
vll z_algo(string pattern, string text) {//z algorithm 最長共通接頭辞
string str = pattern + "$" + text;
ll n = str.length(),np=pattern.sz;
vll Z(n+5),ret(n+5);
for (ll i = 1,L=0,R=0,j; i < n; ++i) {
if (R<i) {
L = R = i;
while (R<n && str[R-L] == str[R])
R++;
Z[i] = R-L;
if(i>np)
ret[i-np-1]=Z[i];
R--;
}else{
j= i-L;
if (Z[j]<R-i+1){
Z[i]=Z[j];
}else{
L = i;
while (R<n && str[R-L] == str[R])
R++;
Z[i] = R-L;
R--;
}
if(i>np)
ret[i-np-1]=Z[i];
}
}
//ff("z"); ou(Z);
re ret;
}
// 2^10 = 1024
//vll dy={-1,-1,-1,0,0,1,1,1},dx={-1,0,1,-1,1,-1,0,1};
/* O(2*10^8) 9*10^18 1LL<<62 4*10^18
~~(v.be,v.be+n,x); not include v.be+n
set.lower_bound(x);
->. *++~ ! /%* +- << < == & && +=?:
*/
// 12345678901234567890
//vll dy={-1,0,0,1},dx={0,-1,1,0};
const ll INF = mod * mod;
typedef pair<int, int>P;
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rp(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
ll mod_pow(ll x, ll n, ll m = mod) {
if (n < 0) {
ll res = mod_pow(x, -n, m);
return mod_pow(res, m - 2, m);
}
if (abs(x) >= m)x %= m;
if (x < 0)x += m;
//if (x == 0)return 0;
ll res = 1;
while (n) {
if (n & 1)res = res * x % m;
x = x * x % m; n >>= 1;
}
return res;
}
//mod should be <2^31
struct mint {
int n;
mint() :n(0) { ; }
mint(ll m) {
if (m < 0 || mod <= m) {
m %= mod; if (m < 0)m += mod;
}
n = m;
}
operator int() { return n; }
};
bool operator==(mint a, mint b) { return a.n == b.n; }
bool operator<(mint a, mint b) { return a.n < b.n; }
mint operator+=(mint& a, mint b) { a.n += b.n; if (a.n >= mod)a.n -= (int)mod; return a; }
mint operator-=(mint& a, mint b) { a.n -= b.n; if (a.n < 0)a.n += (int)mod; return a; }
mint operator*=(mint& a, mint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
mint operator+(mint a, mint b) { return a += b; }
mint operator-(mint a, mint b) { return a -= b; }
mint operator*(mint a, mint b) { return a *= b; }
mint operator^(mint a, ll n) {
if (n == 0)return mint(1);
mint res = (a * a) ^ (n / 2);
if (n % 2)res = res * a;
return res;
}
ll inv(ll a, ll p) {
return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
mint operator/(mint a, mint b) { return a * mint(inv(b, mod)); }
mint operator/=(mint& a, mint b) { a = a / b; return a; }
bool operator==(mint a, ll b) {re a==mint(b);}
bool operator<(mint a, ll b) {re a<mint(b);}
mint operator+=(mint& a, ll b) {re a+=mint(b);}
mint operator-=(mint& a, ll b) {re a-=mint(b);}
mint operator*=(mint& a, ll b) {re a*=mint(b);}
mint operator+(mint a, ll b) {re a+mint(b);}
mint operator-(mint a, ll b) {re a-mint(b);}
mint operator*(mint a, ll b) {re a*mint(b);}
mint operator/(mint a, ll b) {re a/mint(b);}
mint operator/=(mint& a, ll b) {re a/=mint(b);}
bool operator==(ll a, mint b) {re mint(a)==b;}
bool operator<(ll a, mint b) {re mint(a)<(b);}
mint operator+(ll a, mint b) {re mint(a)+(b);}
mint operator-(ll a, mint b) {re mint(a)-(b);}
mint operator*(ll a, mint b) {re mint(a)*(b);}
mint operator/(ll a, mint b) {re mint(a)/(b);}
bool operator==(mint a, int b) {re a==mint(b);}
bool operator<(mint a, int b) {re a<mint(b);}
mint operator+=(mint& a, int b) {re a+=mint(b);}
mint operator-=(mint& a, int b) {re a-=mint(b);}
mint operator*=(mint& a, int b) {re a*=mint(b);}
mint operator+(mint a, int b) {re a+mint(b);}
mint operator-(mint a, int b) {re a-mint(b);}
mint operator*(mint a, int b) {re a*mint(b);}
mint operator/(mint a, int b) {re a/mint(b);}
mint operator/=(mint& a, int b) {re a/=mint(b);}
bool operator==(int a, mint b) {re mint(a)==b;}
bool operator<(int a, mint b) {re mint(a)<(b);}
mint operator+(int a, mint b) {re mint(a)+(b);}
mint operator-(int a, mint b) {re mint(a)-(b);}
mint operator*(int a, mint b) {re mint(a)*(b);}
mint operator/(int a, mint b) {re mint(a)/(b);}
//istream &operator >> (istream &is,pnt<dou> &r){is>>r.x>>r.y;return is;}
//ostream &operator << (ostream &os,pnt<dou> &r){os<<r.x<<" "<<r.y;return os;}
istream &operator >> (istream &is, mint &x)
{
ll m;
is >> m;
if (m < 0 || mod <= m) {
m %= mod; if (m < 0)m += mod;
}
x.n = m;
return is;
}
ostream &operator << (ostream &os, mint &i)
{
os << i.n;
return os;
}
const int max_n = 1 << 21;
mint fact[max_n], factinv[max_n];
void init_f() {
fact[0] = mint(1);
for (int i = 0; i < max_n - 1; i++) {
fact[i + 1] = fact[i] * mint(i + 1);
}
factinv[max_n - 1] = mint(1) / fact[max_n - 1];
for (int i = max_n - 2; i >= 0; i--) {
factinv[i] = factinv[i + 1] * mint(i + 1);
}
}
mint comb(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[b] * factinv[a - b];
}
mint combP(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[a - b];
}
ll gcd(ll a, ll b) {
a = abs(a); b = abs(b);
if (a < b)swap(a, b);
while (b) {
ll r = a % b; a = b; b = r;
}
return a;
}
struct HLD {
int n;
vector<int> siz, top, dep, parent, in, out, seq;
vector<vector<int>> adj;
int cur;
HLD() {}
HLD(int n) {
init(n);
}
void init(int n) {//初期化
this->n = n;
siz.resize(n);//部分木のサイズ
top.resize(n);//列の先頭
dep.resize(n);//深さ
parent.resize(n);//親
in.resize(n); //新しい番号
out.resize(n);//部分木の最後の番号+1
seq.resize(n);//order iの頂点はseq[i]
cur = 0;
adj.assign(n, {});//隣接リスト
}
void add(int u, int v) {//辺を追加
adj[u].push_back(v);
adj[v].push_back(u);
}
void work(int root = 0) {//ビルド
top[root] = root;
dep[root] = 0;
parent[root] = -1;
dfs1(root);
dfs2(root);
}
void dfs1(int u) {
if (parent[u] != -1) {
adj[u].erase(find(adj[u].begin(), adj[u].end(), parent[u]));
//親を隣接リストから消す
}
siz[u] = 1;
for (auto &v : adj[u]) {
parent[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
siz[u] += siz[v];
//adj[u][0]をheavyになるようにする
if (siz[v] > siz[adj[u][0]]) {
swap(v, adj[u][0]);
}
}
}
void dfs2(int u) {
in[u] = cur++;//新しい番号を割り振る
seq[in[u]] = u;//order in[u]の頂点はu
for (auto v : adj[u]) {
top[v] = v == adj[u][0] ? top[u] : v;
dfs2(v);
}
out[u] = cur;
}
int lca(int u, int v) {
while (top[u] != top[v]) {//同じ列でない間
if (dep[top[u]] > dep[top[v]]) {//深い方から上る
u = parent[top[u]];
} else {
v = parent[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
int jump(int u, int k) {
if (dep[u] < k) {
return -1;
}
int d = dep[u] - k;
while (dep[top[u]] > d) {
u = parent[top[u]];
}
return seq[in[u] - dep[u] + d];
}
bool isAncester(int u, int v) {
return in[u] <= in[v] && in[v] < out[u];
}
int rootedChild(int u, int v) {
if (u == v) {
return u;
}
if (!isAncester(u, v)) {
return parent[u];
}
auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
return in[x] < in[y];
}) - 1;
return *it;
}
int rootedSize(int u, int v) {
if (u == v) {
return n;
}
if (!isAncester(v, u)) {
return siz[v];
}
return n - siz[rootedChild(v, u)];
}
int rootedLca(int a, int b, int c) {
return lca(a, b) ^ lca(b, c) ^ lca(c, a);
}
};
void init(){
ios::sync_with_stdio(false);
cin.tie(0);
}
void solve(){
//ge(ll,t);
ll t=1;
xx(t){
sub();
}
}
/* Rerooting: 全方位木 DP
問題ごとに以下を書き換える
- 型DPと単位元
- 型DPに対する二項演算 merge
- まとめたDPを用いて新たな部分木のDPを計算する add_root
計算量: O(N)
*/
vll vc;
struct Rerooting {
/* start 問題ごとに書き換え */
struct DP { // DP の型
long long dp;
ll s=0;
DP(long long dp_) : dp(dp_){}
DP(long long dp_,ll s_) : dp(dp_),s(s_){}
};
const DP identity = DP(0); // 単位元(末端の値は add_root(identity) になるので注意)
function<DP(DP, DP)> merge = [](DP dp_cum, DP d) -> DP {
return DP(dp_cum.dp + d.dp ,dp_cum.s+d.s);
};
struct Edge {
int to;
};
function<DP(DP,ll)> add_root = [](DP d,ll v) -> DP {
return DP(d.dp+d.s , vc[v]+d.s );
};
/* end 問題ごとに書き換え */
// グラフの定義
using Graph = vector<vector<Edge>>;
vector<vector<DP>> dp; // dp[v][i]: vから出るi番目の有向辺に対応する部分木のDP
vector<DP> ans; // ans[v]: 頂点vを根とする木の答え
Graph G;
Rerooting(int N) : G(N) {//ここからスタート
dp.resize(N);
ans.assign(N, identity);
}
void add_edge(int a, int b) {
G[a].push_back({b});
}
void build() {
dfs(0); // 普通に木DP
bfs(0, identity); // 残りの部分木に対応するDPを計算
}
DP dfs(int v, int p = -1) { // 頂点v, 親p
DP dp_cum = identity;
int deg = G[v].size();//次数
dp[v] = vector<DP>(deg, identity);//vを根とする
for (int i = 0; i < deg; i++) {
int u = G[v][i].to;
if (u == p) continue;
dp[v][i] = dfs(u, v);
dp_cum = merge(dp_cum, dp[v][i]);
}
return add_root(dp_cum,v);
}
void bfs(int v, const DP& dp_p, int p = -1) { // bfs だが、実装が楽なので中身は dfs になっている
int deg = G[v].size();
for (int i = 0; i < deg; i++) { // 前のbfsで計算した有向辺に対応する部分木のDPを保存
if (G[v][i].to == p) dp[v][i] = dp_p;
}
vector<DP> dp_l(deg + 1, identity), dp_r(deg + 1, identity); // 累積merge
for (int i = 0; i < deg; i++) {
dp_l[i + 1] = merge(dp_l[i], dp[v][i]);
}
for (int i = deg - 1; i >= 0; i--) {
dp_r[i] = merge(dp_r[i + 1], dp[v][i]);
}
ans[v] = add_root(dp_l[deg],v); // 頂点 v の答え
for (int i = 0; i < deg; i++) { // 一つ隣の頂点に対しても同様に計算
int u = G[v][i].to;
if (u == p) continue;
bfs(u, add_root(merge(dp_l[i], dp_r[i + 1]),v), v);
}
}
};
/* SegTreeLazy<X,M>(n,fx,fa,fm,ex,em): モノイド(集合X, 二項演算fx,fa,fm, 単位元ex,em)についてサイズnで構築
set(int i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
update(l,r,x): [l,r) O(log(n))
query(a,b): [a,b) 全てにfxを作用させた値を取得。O(log(n))
*/
/* SegTreeLazy<X,M>(n,fx,fa,fm,ex,em): モノイド(集合X, 二項演算fx,fa,fm, 単位元ex,em)についてサイズnで構築
set(int i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
update(l,r,x): [l,r) O(log(n))
query(a,b): [a,b) 全てにfxを作用させた値を取得。O(log(n))
*/
struct segtree {
struct X{
ll x=0;//長さ
X(ll _x):x(_x){;}
X():x(0){;}
bool operator==(X r) {re r.x==x;}
};
X opx(X x1,X x2)
{
return max(x1.x,x2.x);
}
X ex=X(0);
using FX = function<X(X, X)>;
int n;
vector<X> dat;
segtree(int n_):dat(n_*4,ex){
int x = 1;
while (n_ > x) x *= 2;
n = x;
//fl("n",n);
}
void set(int i, X x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = opx(dat[2 * k + 1], dat[2 * k + 2]);
}
void update(int i, X x) {
i += n - 1;
dat[i] = x;
while (i > 0) {
i = (i - 1) / 2; // parent
dat[i] = opx(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
X query_sub(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) { // 完全に外側の時
return ex;
} else if (a <= l && r <= b) { // 完全に内側の時
return dat[k];
} else { // 一部区間が被る時
X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return opx(vl, vr);
}
}
X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
};
#define rep(i,n) for (int i = 0; i < (n); ++i)
// Coodinate Compression
// https://youtu.be/fR3W5IcBGLQ?t=8550
template<typename T=ll>
struct CC {
bool initialized;
vector<T> xs;
CC(): initialized(false) {}
void add(T x) { xs.push_back(x);}
void init() {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
initialized = true;
}
int operator()(T x) {
if (!initialized) init();
return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
}
T operator[](int i) {
if (!initialized) init();
return xs[i];
}
int size() {
if (!initialized) init();
return xs.size();
}
};
struct lazy {
struct X{
//a*x+b;
ll x=1;
X(ll _x):x(_x){;}
bool operator==(X r) {re r.x==x;}
};
struct A
{
ll a=1;
A(ll _a):a(_a){;}
bool operator==(A r) {re a==r.a;}
};
X opx(X x1,X x2)
{
return x1.x&&x2.x;
}
X ex=X(1ll);
X opax(A a,X x)
{
return a.a&&x.x;
}
A opa(A a1,A a2)
{
a1.a=a1.a&&a2.a;
return a1;
}
A ea=A(1);
using FX = function<X(X, X)>;
using FAX = function<X(A,X)>;
using FA = function<A(A, A)>;
int n;
vector<X> dat;
vector<A> v_lazy;
lazy(int n_):dat(n_*4,ex),v_lazy(n_*4,ea){
int x = 1;
while (n_ > x) x *= 2;
n = x;
//fl("n",n);
}
void set(int i, X x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = opx(dat[2 * k + 1], dat[2 * k + 2]);
}
/* lazy eval */
void eval(int k) {
if (v_lazy[k] == ea) return; // 更新するものが無ければ終了
if (k < n - 1) { // 葉でなければ子に伝搬
v_lazy[k * 2 + 1] = opa(v_lazy[k * 2 + 1], v_lazy[k]);
v_lazy[k * 2 + 2] = opa(v_lazy[k * 2 + 2], v_lazy[k]);
}
// 自身を更新
dat[k] = opax(v_lazy[k],dat[k]);
v_lazy[k] = ea;
}
void update(int a, int b, A x, int k, int l, int r) {
eval(k);
if (a <= l && r <= b) { // 完全に内側の時
v_lazy[k] = opa(v_lazy[k], x);
eval(k);
} else if (a < r && l < b) { // 一部区間が被る時
update(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子
update(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子
dat[k] = opx(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void update(int L, int R, A a) { update(L, R, a, 0, 0, n); }
void update(int L, int R, ll a) {
A Aa=A(a);
update(L, R, Aa, 0, 0, n); }
X query_sub(int a, int b, int k, int l, int r) {
eval(k);
if (r <= a || b <= l) { // 完全に外側の時
return ex;
} else if (a <= l && r <= b) { // 完全に内側の時
return dat[k];
} else { // 一部区間が被る時
X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return opx(vl, vr);
}
}
X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
};
void sub() {
ge(ll,n);
vec<vll>e(n);
i(n)
{
ge(ll,m);
j(m)
{
ge(ll,to);
--to;
e[i].pub(to);
}
}
vll vis(n);
function<void(ll)>f=[&](ll now)
{
vis[now]=1;
for(ll to:e[now])if(vis[to]==0)
f(to);
};
f(0);
ll ok=1;
i(n)
ok&=vis[i];
Yes(ok);
}