結果

問題 No.901 K-ary εxtrεεmε
ユーザー hirayuu_ychirayuu_yc
提出日時 2024-04-29 09:34:26
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 385 ms / 3,000 ms
コード長 14,720 bytes
コンパイル時間 5,015 ms
コンパイル使用メモリ 307,156 KB
実行使用メモリ 48,344 KB
最終ジャッジ日時 2024-11-18 11:59:36
合計ジャッジ時間 14,781 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 157 ms
48,344 KB
testcase_01 AC 3 ms
6,820 KB
testcase_02 AC 5 ms
6,820 KB
testcase_03 AC 4 ms
6,820 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 4 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 301 ms
47,232 KB
testcase_08 AC 312 ms
47,224 KB
testcase_09 AC 309 ms
47,360 KB
testcase_10 AC 313 ms
47,224 KB
testcase_11 AC 317 ms
47,232 KB
testcase_12 AC 309 ms
47,232 KB
testcase_13 AC 311 ms
47,104 KB
testcase_14 AC 308 ms
47,228 KB
testcase_15 AC 307 ms
47,368 KB
testcase_16 AC 306 ms
47,360 KB
testcase_17 AC 351 ms
47,360 KB
testcase_18 AC 313 ms
47,232 KB
testcase_19 AC 304 ms
47,220 KB
testcase_20 AC 333 ms
47,100 KB
testcase_21 AC 307 ms
47,216 KB
testcase_22 AC 346 ms
47,232 KB
testcase_23 AC 379 ms
47,352 KB
testcase_24 AC 334 ms
47,240 KB
testcase_25 AC 324 ms
47,356 KB
testcase_26 AC 309 ms
47,356 KB
testcase_27 AC 299 ms
47,108 KB
testcase_28 AC 304 ms
47,236 KB
testcase_29 AC 385 ms
47,232 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/root/AtCoder/Halc-Library/Tree/StaticTopTree.hpp: In member function 'int32_t StaticTopTree<M>::_merge(std::vector<int>&, std::vector<int>&, int32_t, int32_t, bool) [with M = steiner]':
/root/AtCoder/Halc-Library/Tree/StaticTopTree.hpp:112:5: warning: control reaches end of non-void function [-Wreturn-type]

ソースコード

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

#line 1 "main.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/901"
#line 2 "/root/AtCoder/Halc-Library/Template.hpp"
//https://tatyam.hatenablog.com/entry/2019/12/15/003634
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> using pq=priority_queue<T,vector<T>,greater<T>>;
using pll=pair<ll,ll>;
const ll LINF=1LL<<60;
#define _overload3(_1,_2,_3,name,...) name
#define _overload4(_1,_2,_3,_4,name,...) name
#define _rep1(i,n) for(ll i=0; i<(n); i++)
#define _rep2(i,a,b) for(ll i=(a); i<(b); i++)
#define _rep3(i,a,b,c) for(ll i=(a); i<(b); i+=(c))
#define rep(...) _overload4(__VA_ARGS__,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define _rrep1(i,n) for(ll i=(n); i-->0;)
#define _rrep2(i,a,b) for(ll i=(b); i-->(a);)
#define rrep(...) _overload3(__VA_ARGS__,_rrep2,_rrep1)(__VA_ARGS__)
#define each(i,...) for(auto&& i:__VA_ARGS__)
#define all(i) begin(i),end(i)
#define rall(i) rbegin(i),rend(i)
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return true;}else return false;}
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return true;}else return false;}
template<class T> ll sum(const T &a){return accumulate(all(a),0LL);}
template<class T> auto min(const T &a){return *min_element(all(a));}
template<class T> auto max(const T &a){return *max_element(all(a));}
inline int scan(){ return getchar(); }
inline void scan(int &a){ scanf("%d", &a); }
inline void scan(unsigned &a){ scanf("%u", &a); }
inline void scan(long &a){ scanf("%ld", &a); }
inline void scan(long long &a){ scanf("%lld", &a); }
inline void scan(unsigned long long &a){ scanf("%llu", &a); }
inline void scan(char &a){ cin >> a; }
inline void scan(float &a){ scanf("%f", &a); }
inline void scan(double &a){ scanf("%lf", &a); }
inline void scan(long double &a){ scanf("%Lf", &a); }
inline void scan(vector<bool> &vec){ for(unsigned i = 0; i < vec.size(); i++) { int a; scan(a); vec[i] = a; } }
inline void scan(char a[]){ scanf("%s", a); }
inline void scan(string &a){ cin >> a; }
template<class T> inline void scan(vector<T> &vec);
template<class T, size_t size> inline void scan(array<T, size> &vec);
template<class T, class L> inline void scan(pair<T, L> &p);
template<class T, size_t size> inline void scan(T (&vec)[size]);
template<class T> inline void scan(vector<T> &vec){ for(auto &i : vec) scan(i); }
template<class T> inline void scan(deque<T> &vec){ for(auto &i : vec) scan(i); }
template<class T, size_t size> inline void scan(array<T, size> &vec){ for(auto &i : vec) scan(i); }
template<class T, class L> inline void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
template<class T, size_t size> inline void scan(T (&vec)[size]){ for(auto &i : vec) scan(i); }
template<class T> inline void scan(T &a){ cin >> a; }
inline void in(){}
template <class Head, class... Tail> inline void in(Head &head, Tail&... tail){ scan(head); in(tail...); }
inline void print(){ putchar(' '); }
inline void print(const bool &a){ printf("%d", a); }
inline void print(const int &a){ printf("%d", a); }
inline void print(const unsigned &a){ printf("%u", a); }
inline void print(const long &a){ printf("%ld", a); }
inline void print(const long long &a){ printf("%lld", a); }
inline void print(const unsigned long long &a){ printf("%llu", a); }
inline void print(const char &a){ printf("%c", a); }
inline void print(const char a[]){ printf("%s", a); }
inline void print(const float &a){ printf("%.15f", a); }
inline void print(const double &a){ printf("%.15f", a); }
inline void print(const long double &a){ printf("%.15Lf", a); }
inline void print(const string &a){ for(auto&& i : a) print(i); }
template<class T> inline void print(const vector<T> &vec);
template<class T, size_t size> inline void print(const array<T, size> &vec);
template<class T, class L> inline void print(const pair<T, L> &p);
template<class T, size_t size> inline void print(const T (&vec)[size]);
template<class T> inline void print(const vector<T> &vec){ if(vec.empty()) return; print(vec[0]); for(auto i = vec.begin(); ++i != vec.end(); ){
    putchar(' '); print(*i); } }
template<class T> inline void print(const deque<T> &vec){ if(vec.empty()) return; print(vec[0]); for(auto i = vec.begin(); ++i != vec.end(); ){
    putchar(' '); print(*i); } }
template<class T, size_t size> inline void print(const array<T, size> &vec){ print(vec[0]); for(auto i = vec.begin(); ++i != vec.end(); ){ putchar('
    '); print(*i); } }
template<class T, class L> inline void print(const pair<T, L> &p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> inline void print(const T (&vec)[size]){ print(vec[0]); for(auto i = vec; ++i != end(vec); ){ putchar(' '); print(*i);
    } }
template<class T> inline void print(const T &a){ cout << a; }
inline int out(){ putchar('\n'); return 0; }
template<class T> inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> inline int out(const Head &head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
using ld=long double;
using ull=unsigned long long;
using uint=unsigned int;
using pii=pair<int,int>;
using pdd=pair<ld,ld>;
using tuplis=array<ll,3>;
#define vec(type,name,...) vector<type> name(__VA_ARGS__);
#define vv(type,name,h,...)vector<vector<type>> name(h,vector<type>(__VA_ARGS__));
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size); in(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
template<class T> ld dsum(const T &a){return accumulate(all(a),0.0L);}
const int INF=INT_MAX>>1;
const ll MINF=1LL<<40;
const ld DINF=numeric_limits<ld>::infinity();
const int MODD=1000000007;
const int MOD=998244353;
const ld EPS=1e-9;
const ld PI=3.1415926535897932;
const ll four[]={0,1,0,-1,0};
const ll eight[]={0,1,1,0,-1,-1,1,-1,0};
ll intpow(ll a,ll b){ll ret=1;while(b){if(b&1)ret*=a;a*=a;b>>=1;}return ret;}
int Yes(bool i=true){return out(i?"Yes":"No");}
int No(bool i=true){return out(i?"No":"Yes");}
#define len(x) ((int)(x).size())
#define fi first
#define se second
#line 2 "/root/AtCoder/Halc-Library/Tree/StaticTopTree.hpp"
template<class M>
struct StaticTopTree{
using point=M::point;
using path=M::path;
struct Node{
bool is_path;
point point_val;
path path_val;
int32_t pos;
int32_t left;
int32_t right;
int32_t parent;
Node(bool pat,int32_t po=-1,int32_t lf=-1,int32_t ri=-1){
is_path=pat;
pos=po;
left=lf;
right=ri;
parent=-1;
}
};
size_t sz;
vector<vector<int32_t>> tree;
vector<int32_t> node_pos;
vector<Node> nodes;
int32_t rt;
StaticTopTree(size_t size){
sz=size;
tree.resize(sz);
node_pos.resize(sz);
}
void add_edge(int32_t s,int32_t v){
tree[s].emplace_back(v);
tree[v].emplace_back(s);
}
int32_t _path_cluster(int32_t pos,vector<int32_t> &tree_sz){
if(tree[pos].empty()){
node_pos[pos]=nodes.size();
nodes.emplace_back(Node(1,pos));
_calc_val(nodes.size()-1);
return nodes.size()-1;
}
vector<int32_t> address;
vector<int32_t> sizes;
while(!tree[pos].empty()){
int32_t max_size=-1;
int32_t next_pos=-1;
for(int i=0; i<tree[pos].size(); i++){
if(tree_sz[tree[pos][i]]>max_size){
max_size=tree_sz[tree[pos][i]];
next_pos=i;
}
}
swap(tree[pos][next_pos],tree[pos].back());
next_pos=tree[pos].back();
tree[pos].pop_back();
tree_sz[pos]-=tree_sz[next_pos];
sizes.emplace_back(tree_sz[pos]);
address.emplace_back(_point_cluster(pos,tree_sz));
pos=next_pos;
}
address.emplace_back(_point_cluster(pos,tree_sz));
sizes.emplace_back(tree_sz[pos]);
return _merge(address,sizes,0,address.size(),1);
}
int32_t _point_cluster(int32_t pos,vector<int32_t> &tree_sz){
if(tree[pos].empty()){
node_pos[pos]=nodes.size();
nodes.emplace_back(Node(1,pos));
_calc_val(nodes.size()-1);
return nodes.size()-1;
}
vector<int32_t> address;
vector<int32_t> sizes;
for(int32_t i:tree[pos]){
sizes.emplace_back(tree_sz[i]);
int32_t vert=_path_cluster(i,tree_sz);
nodes.emplace_back(Node(0,-1,vert));
nodes[vert].parent=nodes.size()-1;
address.emplace_back(nodes.size()-1);
_calc_val(nodes.size()-1);
}
int32_t vert=_merge(address,sizes,0,address.size(),0);
node_pos[pos]=nodes.size();
nodes.emplace_back(Node(1,pos,vert));
nodes[vert].parent=nodes.size()-1;
_calc_val(nodes.size()-1);
return nodes.size()-1;
}
int32_t _merge(vector<int32_t> &address,vector<int32_t> &sizes,int32_t lf,int32_t ri,bool pat){
if(lf+1==ri)return address[lf];
int32_t add=0;
for(int32_t i=lf; i<ri; i++){
add+=sizes[i];
}
int32_t now=0;
int32_t bef=add+1;
for(int32_t i=lf; i<ri; i++){
now+=sizes[i];
if(now>add-now){
if(now+now-add>bef)i--;
int32_t left=_merge(address,sizes,lf,i+1,pat);
int32_t right=_merge(address,sizes,i+1,ri,pat);
nodes.emplace_back(Node(pat,-1,left,right));
nodes[left].parent=nodes.size()-1;
nodes[right].parent=nodes.size()-1;
_calc_val(nodes.size()-1);
return nodes.size()-1;
}
bef=add-now-now;
}
}
void _calc_val(int32_t pos){
if(nodes[pos].is_path){
if((nodes[pos].left==-1) && (nodes[pos].right==-1)){
nodes[pos].path_val=M::vertex(nodes[pos].pos);
}
else if((nodes[pos].left!=-1) && (nodes[pos].right!=-1)){
nodes[pos].path_val=M::compress(nodes[nodes[pos].left].path_val,nodes[nodes[pos].right].path_val);
}
else{
nodes[pos].path_val=M::add_vertex(nodes[nodes[pos].left].point_val,nodes[pos].pos);
}
}
else{
if((nodes[pos].left!=-1) && (nodes[pos].right!=-1)){
nodes[pos].point_val=M::rake(nodes[nodes[pos].left].point_val,nodes[nodes[pos].right].point_val);
}
else{
nodes[pos].point_val=M::add_edge(nodes[nodes[pos].left].path_val);
}
}
}
void build(int32_t root){
vector<int32_t> vert(sz);
vector<int32_t> tree_sz(sz,-1);
vert[0]=root;
tree_sz[0]=0;
int32_t cnt=1;
for(int32_t i=0; i<sz; i++){
for(int32_t j:tree[vert[i]]){
if(tree_sz[j]){
tree_sz[j]=0;
vert[cnt]=j;
cnt++;
}
}
}
for(int32_t i=sz-1; i>=0; i--){
int32_t parent=0;
for(int32_t j:tree[vert[i]]){
if(tree_sz[j]==0){
parent=-parent-1;
}
if(parent>=0)parent++;
tree_sz[vert[i]]+=tree_sz[j];
}
if(parent<0){
swap(tree[vert[i]][-parent-1],tree[vert[i]].back());
tree[vert[i]].pop_back();
}
tree_sz[vert[i]]++;
}
rt=_path_cluster(root,tree_sz);
}
path root_value(){
return nodes[rt].path_val;
}
void calc(int32_t pos){
int32_t change=node_pos[pos];
while(nodes[change].parent!=-1){
_calc_val(change);
change=nodes[change].parent;
}
_calc_val(change);
}
size_t size(){
return sz;
}
};
#line 4 "main.cpp"
vector<bool> mark;
vector<ll> weight;
struct steiner{
using point=array<ll,5>;
using path=array<ll,6>;
static path vertex(int v){
if(mark[v]){
return {1,0,0,0,0,weight[v]};
}
return {0,0,0,0,0,weight[v]};
}
static path compress(path p,path c){
if(p[0]==0 && c[0]==0){
return {0,0,0,p[3]+c[3]+c[5],p[3]+c[3]+c[5],p[5]};
}
if(p[0]==1 && c[0]==0){
return {1,p[1],p[2],p[3],p[4]+c[3]+c[5],p[5]};
}
if(p[0]==0 && c[0]==1){
return {1,c[1],c[2],p[3]+c[3]+c[5],c[4],p[5]};
}
return {1,p[2]+c[2]+p[4]+c[3]+c[5],p[2]+c[2]+p[4]+c[3]+c[5],p[3],c[4],p[5]};
}
static path add_vertex(point t,int v){
if(t[0]==0){
if(mark[v]){
return {1,0,0,0,0,weight[v]};
}
return {0,0,0,0,0,weight[v]};
}
if(t[3]==0){
if(mark[v]){
return {1,t[2]+t[4],t[2]+t[4],0,0,weight[v]};
}
return {1,t[1],t[2]+t[4],0,0,weight[v]};
}
return {1,t[2]+t[4],t[2]+t[4],0,0,weight[v]};
}
static point rake(point x,point y){
if(x[0]<y[0])swap(x,y);
if(x[0]==0 && y[0]==0){
return {0,0,0,0,0};
}
if(x[0]==1 && y[0]==0){
return x;
}
return {1,x[2]+y[2],x[2]+y[2],1,x[4]+y[4]};
}
static point add_edge(path t){
if(t[0]==0){
return {0,0,0,0,0};
}
return {1,t[1],t[2]+t[3],0,t[5]};
}
};
void solve(){
LL(N);
StaticTopTree<steiner> tree(N);
vv(pll,gr,N);
rep(i,N-1){
LL(u,v,w);
tree.add_edge(u,v);
gr[u].push_back(pll(v,w));
gr[v].push_back(pll(u,w));
}
mark.resize(N,0);
weight.resize(N,-1);
weight[0]=0;
stack<ll> vert;
vert.push(0);
while(!vert.empty()){
ll pos=vert.top();
vert.pop();
for(auto &[t,w]:gr[pos]){
if(weight[t]==-1){
weight[t]=w;
vert.push(t);
}
}
}
tree.build(0);
LL(Q);
rep(i,Q){
LL(k);
VEC(ll,x,k);
each(j,x){
mark[j]=1;
tree.calc(j);
}
out(tree.root_value()[1]);
each(j,x){
mark[j]=0;
tree.calc(j);
}
}
}
int main(){
solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0