結果

問題 No.399 動的な領主
ユーザー momoyuumomoyuu
提出日時 2023-03-21 21:03:01
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,097 ms / 2,000 ms
コード長 3,843 bytes
コンパイル時間 3,465 ms
コンパイル使用メモリ 263,240 KB
実行使用メモリ 23,552 KB
最終ジャッジ日時 2024-09-18 14:30:50
合計ジャッジ時間 13,292 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 6 ms
5,376 KB
testcase_05 AC 62 ms
5,376 KB
testcase_06 AC 1,044 ms
16,000 KB
testcase_07 AC 1,080 ms
15,872 KB
testcase_08 AC 1,028 ms
15,872 KB
testcase_09 AC 1,034 ms
15,872 KB
testcase_10 AC 8 ms
6,940 KB
testcase_11 AC 46 ms
6,944 KB
testcase_12 AC 705 ms
16,384 KB
testcase_13 AC 677 ms
16,256 KB
testcase_14 AC 187 ms
23,552 KB
testcase_15 AC 323 ms
23,552 KB
testcase_16 AC 469 ms
19,840 KB
testcase_17 AC 1,097 ms
15,872 KB
testcase_18 AC 1,051 ms
15,872 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template< typename T1, typename T2 = T1 >
struct lazysegtree{
using F1 = function<T1(T1,T1)>;
using F2 = function<T2(T2,T2)>;
//using F3 = function<T1(T2,T1)>;
using F3 = function<T1(T2,T1,int,int)>;
int n;
F1 f1;
F2 f2;
F3 f3;
T1 e1;
T2 e2,e3;
vector<T1> data;
vector<T2> lazy;//ソ
vector<int> p;//ΛーW
/*
* n:
* f1:∫エ」ォf2:」ォ,f3:
* e:
*/
lazysegtree(int _n,F1 f1,F2 f2,F3 f3,T1 e1,T2 e2,T2 e3):f1(f1),f2(f2),f3(f3),e1(e1),e2(e2),e3(e3){
n = 1;
while(n<_n) n<<=1;
data.assign(2*n,e1);
lazy.assign(2*n,e3);
p.assign(2*n,0);
}
void set(int i,T1 x){
data[i+n-1] = x;
}
void build(){
for(int i = n - 2;i>=0;i--){
data[i] = f1(data[2*i+1],data[2*i+2]);
}
}
void rangeupdate(T2 x,int a,int b,int ni,int l,int r){
update(ni,l,r);
if(b<=l||r<=a) return;
if(a<=l&&r<=b){
p[ni] = 1;
lazy[ni] = f2(x,lazy[ni]);
update(ni,l,r);
}else{
rangeupdate(x,a,b,2*ni+1,l,(l+r)/2);
rangeupdate(x,a,b,2*ni+2,(l+r)/2,r);
if(l+1<r) data[ni] = f1(data[2*ni+1],data[2*ni+2]);
}
}
void rangeupdate(T2 x,int a,int b){
rangeupdate(x,a,b,0,0,n);
}
void update(int ni,int l,int r){
if(!p[ni])return;
p[ni] = 0;
//data[ni] = f3(lazy[ni],data[ni]);
data[ni] = f3(lazy[ni],data[ni],l,r);
if(l+1<r){
p[2*ni+1] = 1;
p[2*ni+2] = 1;
lazy[2*ni+1] = f2(lazy[ni],lazy[2*ni+1]);
lazy[2*ni+2] = f2(lazy[ni],lazy[2*ni+2]);
}
lazy[ni] = e3;
}
T1 query(int a,int b,int ni,int l,int r){
update(ni,l,r);
if(b<=l||r<=a) return e1;
if(a<=l&&r<=b) return data[ni];
else return f1(query(a,b,2*ni+1,l,(l+r)/2),query(a,b,2*ni+2,(r+l)/2,r));
}
T1 query(int a,int b){
return query(a,b,0,0,n);
}
T1 operator[](const int i) const {
return data[i+n-1];
}
};
const int mx = 1e5 + 10;
int in[mx],out[mx],par[mx],head[mx],sz[mx];
vector<int> g[mx];
int n;
ll c1(ll a,ll b){
return a+ b;
}
ll c2(ll a,ll b){
return a + b;
}
ll c3(ll a,ll b,ll l,ll r){
return a * (r-l) + b;
}
int sdfs(int ni,int p){
sz[ni] = 1;
par[ni] = p;
if(g[ni].size()&&g[ni][0]==p) swap(g[ni][0],g[ni].back());
for(auto&to:g[ni]){
if(to==p) continue;
sz[ni] += sdfs(to,ni);
if(sz[to]>sz[g[ni][0]]) swap(to,g[ni][0]);
}
return sz[ni];
}
void hdfs(int ni,int p,int&time){
in[ni] = time++;
for(auto&to:g[ni]){
if(to==p) continue;
head[to] = (g[ni][0]==to?head[ni]:to);
hdfs(to,ni,time);
}
out[ni] = time;
}
int main(){
cin>>n;
for(int i = 1;i<n;i++){
int u,v;
cin>>u>>v;
u--;v--;
g[u].push_back(v);
g[v].push_back(u);
}
lazysegtree<ll> seg(n,c1,c2,c3,0LL,0LL,0LL);
seg.rangeupdate(1,0,n);
sdfs(0,-1);
int time = 0;
hdfs(0,-1,time);
ll ans = 0;
int q;
cin>>q;
while(q--){
//cout<<q<<endl;
int u,v;
cin>>u>>v;
u--;v--;
for(;;v=par[head[v]]){
//cout<<u<<" "<<v<<endl;
if(in[u]>in[v]) swap(u,v);
if(head[u]==head[v]) break;
ans += seg.query(in[head[v]],in[v]+1);
seg.rangeupdate(1,in[head[v]],in[v]+1);
}
ans += seg.query(in[u],in[v]+1);
seg.rangeupdate(1,in[u],in[v]+1);
}
cout<<ans<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0