QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#177296 | #5313. Please Save Pigeland | ExplodingKonjac | WA | 728ms | 52064kb | C++17 | 6.9kb | 2023-09-12 20:00:03 | 2023-09-12 20:00:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<16;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
};
class FastOutput final: public FastIOBase
{
private:
void __putc(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE) flush();
#else
putc(x,target);
#endif
}
template<typename T>
void __write(T x)
{
char stk[64],*top=stk;
if(x<0) return __putc('-'),__write(-x);
do *(top++)=x%10,x/=10; while(x);
for(;top!=stk;__putc(*(--top)+'0'));
}
public:
FastOutput(FILE *f=stdout): FastIOBase(f) {}
#ifdef OPENIOBUF
~FastOutput() { flush(); }
void flush() { fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
FastOutput &operator <<(char x)
{ return __putc(x),*this; }
FastOutput &operator <<(const char *s)
{ for(;*s;__putc(*(s++)));return *this; }
FastOutput &operator <<(const std::string &s)
{ return (*this)<<s.c_str(); }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastOutput&> operator <<(const T &x)
{ return __write(x),*this; }
template<typename ...T>
void writesp(const T &...x)
{ std::initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
template<typename ...T>
void writeln(const T &...x)
{ std::initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
template<typename Iter>
void writesp(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<' '; }
template<typename Iter>
void writeln(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<'\n'; }
}qout;
class FastInput final: public FastIOBase
{
private:
bool __eof;
public:
FastInput(FILE *f=stdin): FastIOBase(f),__eof(false)
#ifdef OPENIOBUF
{ buf_p=BUFSIZE; }
void flush() { buf[fread(buf,1,BUFSIZE,target)]=EOF,buf_p=0; }
bool eof()const { return buf[buf_p]==EOF; }
#else
{}
bool eof()const { return feof(target); }
#endif
char get()
{
if(__eof) return EOF;
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
char ch=buf[buf_p++];
#else
char ch=getc(target);
#endif
return ~ch?ch:(__eof=true,EOF);
}
void unget(char c)
{
__eof=false;
#ifdef OPENIOBUF
buf_p--;
#else
ungetc(c,target);
#endif
}
explicit operator bool()const { return !__eof; }
FastInput &operator >>(char &x)
{ while(isspace(x=get()));return *this; }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastInput&> operator >>(T &x)
{
char ch,sym=0;x=0;
while(isspace(ch=get()));
if(__eof) return *this;
if(ch=='-') sym=1,ch=get();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=get());
return unget(ch),sym?x=-x:x,*this;
}
FastInput &operator >>(char *s)
{
while(isspace(*s=get()));
if(__eof) return *this;
for(;!isspace(*s) && !__eof;*(++s)=get());
return unget(*s),*s='\0',*this;
}
FastInput &operator >>(std::string &s)
{
char str_buf[(1<<8)+1]={0},*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=get()));
if(__eof) return *this;
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=get()) && !__eof;p++);
if(p!=buf_end) break;
s.append(str_buf);
}
unget(*p),*p='\0',s.append(str_buf);
return *this;
}
template<typename ...T>
void read(T &...x)
{ std::initializer_list<int>{(this->operator>>(x),0)...}; }
template<typename Iter>
void read(Iter begin,Iter end)
{ while(begin!=end) (*this)>>*(begin++); }
}qin;
} // namespace FastIO
using FastIO::qin,FastIO::qout;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#define LOG(...) void()
#else
#define FILEIO(file)
#define LOG(...) fprintf(stderr,__VA_ARGS__)
#endif
int n,m;
bool vis[500005];
vector<pair<int,int>> G[500005];
class DataSet
{
private:
vector<LL> vec;
LL val;
public:
DataSet(): vec{},val{} {}
DataSet(const DataSet &other): vec(other.vec),val(other.val) {}
DataSet(DataSet &&other): vec(move(other.vec)),val(other.val) {}
size_t size()const { return vec.size(); }
bool empty()const { return vec.empty(); }
void clear() { vec.clear(),val=0; }
LL query(LL dt=0)const
{
if(vec.empty()) return 0;
return gcd(vec[0]+dt,val);
}
void swap(DataSet &other)
{
std::swap(vec,other.vec);
std::swap(val,other.val);
}
void insert(LL x)
{
if(vec.empty()) return vec.push_back(x);
vec.push_back(x-vec[0]);
val=gcd(val,x-vec[0]);
}
void add(LL x)
{
if(vec.empty()) return;
vec[0]+=x;
}
};
LL f[500005],g[500005];
int siz[500005],son[500005],sonw[500005];
class FSolver
{
private:
void dfs1(int u,int fa=0)
{
siz[u]=vis[u];
for(auto &[v,w]: G[u])
{
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
f[u]+=f[v]+w*siz[v];
}
}
void dfs2(int u,int fa=0)
{
LL sz=vis[u],sm=0;
for(auto &[v,w]: G[u])
{
sz+=siz[v];
sm+=f[v]+w*siz[v];
}
for(auto &[v,w]: G[u])
{
if(v==fa) continue;
siz[u]=sz-siz[v];
f[u]=sm-f[v]-w*siz[v];
dfs2(v,u);
}
siz[u]=sz,f[u]=sm;
}
public:
void main() { dfs1(1),dfs2(1); }
}fsolver;
class GSolver
{
private:
void dfs1(int u,int fa=0)
{
siz[u]=1;
for(auto &[v,w]: G[u])
{
if(v==fa) continue;
dfs1(v,u),siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v,sonw[u]=w;
}
}
void dfs2(int u,DataSet &ds,int op,LL d=0,int fa=0)
{
for(auto &[v,w]: G[u])
if(v!=fa) dfs2(v,ds,op,d+w,u);
if(op==1) g[u]=gcd(g[u],ds.query(d));
else if(vis[u]) ds.insert(d);
}
void solve1(int u,DataSet &cur,int fa=0)
{
if(vis[u]) cur.insert(0);
for(auto &[v,w]: G[u])
{
if(v==fa || v==son[u]) continue;
DataSet nxt;
solve1(v,nxt,u);
dfs2(v,cur,1,w,u);
dfs2(v,cur,2,w,u);
}
g[u]=gcd(g[u],cur.query());
if(son[u])
{
cur.add(sonw[u]);
solve1(son[u],cur,u);
}
}
DataSet solve2(int u,int fa=0)
{
DataSet cur;
if(son[u])
{
solve2(son[u],u).swap(cur);
cur.add(sonw[u]);
}
if(vis[u]) cur.insert(0);
for(auto it=G[u].rbegin();it!=G[u].rend();it++)
{
auto &[v,w]=*it;
if(v==fa || v==son[u]) continue;
solve2(v,u);
dfs2(v,cur,1,w,u);
dfs2(v,cur,2,w,u);
}
g[u]=gcd(g[u],cur.query());
return cur;
}
public:
void main()
{
dfs1(1);
DataSet initial;
solve1(1,initial);
solve2(1);
}
}gsolver;
int main()
{
qin>>n>>m;
for(int i=1,x;i<=m;i++) qin>>x,vis[x]=true;
for(int i=1,u,v,w;i<n;i++)
{
qin>>u>>v>>w;
G[u].emplace_back(v,w);
G[v].emplace_back(u,w);
}
fsolver.main();
gsolver.main();
LL ans=4e18;
for(int i=1;i<=n;i++)
ans=min(ans,f[i]?f[i]/g[i]:0);
qout<<ans*2<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 17900kb
input:
5 3 3 4 5 1 2 2 2 3 4 2 5 4 3 4 6
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 17956kb
input:
10 3 1 7 10 7 6 3 1 8 3 3 6 3 8 6 2 4 1 1 10 6 4 2 8 3 9 10 3 5 10 3
output:
24
result:
ok 1 number(s): "24"
Test #3:
score: 0
Accepted
time: 3ms
memory: 20420kb
input:
1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 65ms
memory: 24084kb
input:
100000 1 79187 72704 72659 15 32741 43496 10 21580 97447 17 55758 36700 21 32116 3643 14 60460 58764 12 75894 50624 7 58295 49393 22 43733 17210 1 58093 68769 15 1086 58916 17 25632 37710 11 49555 92976 8 32547 27060 18 84896 12811 1 3196 1242 16 18870 78236 14 2414 7945 12 48745 15399 1 17648 83791...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 4ms
memory: 18024kb
input:
100 10 3 27 33 45 48 72 76 91 92 100 66 98 4 70 17 2 28 59 4 26 25 3 77 92 1 40 61 2 11 27 2 85 35 1 57 26 1 68 99 4 50 84 1 20 82 3 31 39 1 71 7 4 54 55 4 60 26 4 56 61 2 15 66 3 95 53 2 8 60 4 21 82 1 18 81 2 29 73 3 94 4 1 10 4 4 86 43 1 62 41 1 45 57 1 25 66 3 69 89 2 14 53 3 27 92 1 42 98 4 13 ...
output:
200
result:
ok 1 number(s): "200"
Test #6:
score: 0
Accepted
time: 2ms
memory: 18188kb
input:
100 90 75 17 78 84 52 69 54 24 74 35 58 51 72 7 21 70 93 15 60 87 13 40 23 92 99 53 27 22 91 46 56 86 61 19 44 98 50 28 14 12 55 64 30 80 95 38 18 43 31 89 20 16 8 65 63 79 59 34 97 25 2 11 67 71 29 9 37 76 77 26 39 68 32 62 90 10 85 49 42 45 96 83 94 3 6 100 81 57 88 47 67 65 1 43 78 4 98 71 3 71 2...
output:
1798
result:
ok 1 number(s): "1798"
Test #7:
score: 0
Accepted
time: 0ms
memory: 19144kb
input:
1000 10 111 240 479 530 572 583 644 652 753 869 121 923 2 886 685 4 446 284 4 352 250 1 540 485 2 72 154 4 522 693 3 664 917 4 792 941 3 132 832 4 709 186 3 509 114 2 824 978 2 216 265 2 138 570 1 498 959 4 434 222 1 803 693 1 253 677 4 172 463 3 383 978 2 718 959 3 369 421 4 568 454 4 256 938 1 6 1...
output:
226
result:
ok 1 number(s): "226"
Test #8:
score: 0
Accepted
time: 0ms
memory: 18140kb
input:
1000 957 233 514 228 739 827 85 840 175 766 807 19 276 549 611 145 511 895 121 116 525 280 431 810 629 990 509 542 324 241 801 849 506 178 176 49 528 221 742 444 513 111 505 442 794 107 392 291 674 298 803 198 927 738 590 706 804 860 512 421 618 697 516 335 420 418 288 544 694 330 776 104 510 621 47...
output:
32602
result:
ok 1 number(s): "32602"
Test #9:
score: 0
Accepted
time: 607ms
memory: 48028kb
input:
500000 4 182462 188845 259396 281751 456733 79213 9204078 395954 45205 3919968 454058 310013 734433 433648 435834 3887333 448797 138275 9946222 385528 63721 3037094 44276 184047 1799127 169565 81666 3752583 459111 229807 5534913 374868 374333 8627923 476055 408523 2692999 445258 424229 3038119 92885...
output:
193870600
result:
ok 1 number(s): "193870600"
Test #10:
score: 0
Accepted
time: 728ms
memory: 52064kb
input:
500000 150000 1 4 6 12 19 20 21 24 30 34 35 37 39 40 41 45 47 48 49 51 60 65 71 72 75 80 83 84 90 93 94 96 97 99 105 113 115 125 128 132 135 136 138 139 142 145 146 150 152 159 164 167 179 180 186 188 189 190 195 200 204 205 208 210 211 212 214 217 223 226 230 233 238 243 247 260 263 264 268 269 271...
output:
8719582
result:
ok 1 number(s): "8719582"
Test #11:
score: 0
Accepted
time: 0ms
memory: 18400kb
input:
1000 10 334 271 592 707 890 566 590 450 169 129 784 868 7940645 969 691 6692155 864 76 6691895 853 343 2376735 12 897 7467840 783 560 3342995 908 372 952130 5 843 3055195 531 64 7912240 313 701 2196620 246 52 9831250 808 788 6735060 414 340 168805 278 276 6271820 97 247 2379595 490 459 701440 422 45...
output:
15519516
result:
ok 1 number(s): "15519516"
Test #12:
score: 0
Accepted
time: 0ms
memory: 19000kb
input:
1000 10 935 536 379 686 787 66 829 374 369 957 913 887 7565610 118 846 8734750 109 698 7065147 156 813 2228752 769 869 9612951 887 99 4384470 253 494 6908549 655 124 4406482 242 567 5548735 385 694 8703600 705 894 798435 930 179 9333610 346 83 9417442 621 768 953905 490 586 7780155 149 897 7212005 1...
output:
23133220
result:
ok 1 number(s): "23133220"
Test #13:
score: 0
Accepted
time: 2ms
memory: 19356kb
input:
1000 500 474 953 613 122 585 861 627 461 231 466 197 437 807 645 724 259 221 65 312 263 441 895 643 507 159 279 257 801 577 546 160 706 674 840 433 761 921 818 40 862 535 443 396 75 311 836 959 57 986 603 179 133 110 775 990 269 539 858 153 124 529 979 423 241 561 911 151 223 570 275 586 969 49 390 ...
output:
1414024
result:
ok 1 number(s): "1414024"
Test #14:
score: -100
Wrong Answer
time: 2ms
memory: 18268kb
input:
1000 500 229 839 104 538 821 95 707 79 31 77 279 946 889 851 181 165 819 493 129 448 913 371 441 232 278 750 547 432 482 618 998 787 14 987 886 774 97 549 349 425 867 980 974 317 426 451 307 770 140 628 277 629 154 415 595 337 715 374 900 554 395 358 340 465 578 359 195 449 71 898 184 942 382 535 81...
output:
35514
result:
wrong answer 1st numbers differ - expected: '80274', found: '35514'