QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105741#553. 王国zaneyu#100 ✓124ms37656kbC++234.4kb2023-05-15 10:35:042024-05-26 02:54:51

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 02:54:51]
  • 评测
  • 测评结果:100
  • 用时:124ms
  • 内存:37656kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-15 10:35:04]
  • 提交

answer

/*input
3
1 2 50
2 3 59
4
24 41 93
10 66 43
4
88 28 41
4 30 13
5
4 10 61 100
70 58 34 79
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=4e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":"");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;  
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
vector<pii> v[maxn];
vector<ll> l[maxn],c[maxn];
ll pf[maxn],p2[maxn],ppf[maxn];
int m;
ll get(int a,int b){
    return pf[b]-pf[a];
}
int st[maxn];
ll ans=0;
int tot=0;
void dfs(int u,int p){
    for(auto x:v[u]){
        if(x.f==p) continue;
        dfs(x.f,u);
        st[u]+=st[x.f];
        ans+=2LL*st[x.f]*(tot-st[x.f])%MOD*x.s%MOD;
        ans%=MOD;
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n;
    REP(i,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        v[a].pb({b,c}),v[b].pb({a,c});
    }
    REP(i,n){
        cin>>m;
        --m;
        tot+=m;
        st[i]=m;
        l[i].resize(2*m),c[i].resize(2*m);
        REP(j,m){
            cin>>l[i][j];
            l[i][j+m]=l[i][j];
        }
        REP(j,m){
            cin>>c[i][j];
            c[i][j+m]=c[i][j];
        }
        REP1(j,2*m-1){
            pf[j]=pf[j-1]+l[i][j-1];
            ppf[j]=(ppf[j-1]+pf[j])%MOD;
            MNTO(c[i][j],c[i][j-1]+l[i][j-1]);
        }
        for(int j=2*m-2;j>=0;j--){
            MNTO(c[i][j],c[i][j+1]+l[i][j]);
        }
        REP(j,m) MNTO(c[i][j],c[i][j+m]),MNTO(c[i][j+m],c[i][j]);
        p2[0]=c[i][0];
        REP1(j,2*m-1){
            p2[j]=p2[j-1]+c[i][j];
        }
        REP(j,m){
            int a=j,b=j+m-1;
            while(a<b){
                int mid=(a+b+1)/2;
                if(get(j,mid)<c[i][j]+c[i][mid]){
                    a=mid;
                }
                else b=mid-1;
            }
            int opl=a;
            a=j+1,b=j+m;
            while(a<b){
                int mid=(a+b)/2;
                if(get(mid,j+m)<c[i][j]+c[i][mid]){
                    b=mid;
                }
                else a=mid+1;
            }
            int opr=a;
            if(opl<opr){
                ans+=p2[opr-1]-p2[opl]+1LL*(opr-opl-1)*c[i][j];
                ans+=(ppf[opl]-ppf[j])-1LL*(opl-j)*(pf[j]%MOD)%MOD;
                ans+=pf[j+m]%MOD*(j+m-opr)%MOD-(ppf[j+m-1]-ppf[opr-1]);
            }
            else{
                a=j,b=j+m;
                while(a<b){
                    int mid=(a+b+1)/2;
                    if(get(j,mid)<get(mid,j+m)){
                        a=mid;
                    }
                    else b=mid-1;
                }
                ans+=(ppf[a]-ppf[j])-1LL*(a-j)*(pf[j]%MOD)%MOD;
                ++a;
                ans+=1LL*(pf[j+m]%MOD)*(j+m-a)%MOD-(ppf[j+m-1]-ppf[a-1]);
            }
            ans%=MOD;
            if(ans<0) ans+=MOD;
        }
        ans%=MOD;
    }
    REP(i,n){
        int m=sz(c[i])/2;
        REP(j,m) ans+=2LL*c[i][j]*(tot-m)%MOD;
        ans%=MOD;
    }
    dfs(0,-1);
    cout<<ans<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 2ms
memory: 7692kb

input:

10
1 2 50
2 3 59
2 4 73
1 5 79
4 6 10
1 7 66
1 8 43
4 9 4
8 10 30
8
39 2 72 38 78 95 10
45 98 29 59 98 5 32
10
46 36 43 69 61 95 96 14 7
76 99 100 13 58 9 69 31 63
9
43 83 68 96 72 91 39 17
66 53 22 13 2 32 58 91
14
41 36 73 96 55 90 6 24 14 39 21 67 27
80 7 99 20 24 61 27 7 71 95 45 35 95
10
64 45 ...

output:

1956394

result:

ok single line: '1956394'

Test #2:

score: 10
Accepted
time: 0ms
memory: 7768kb

input:

5
1 2 250
2 3 659
2 4 273
1 5 879
20
439 502 872 138 178 295 610 746 636 143 969 261 595 396 114 7 943 83 768
145 898 829 359 398 905 232 176 299 400 413 558 9 969 531 963 366 853 822
18
696 672 591 739 617 641 336 973 96 455 290 906 124 814 239 221 367
713 902 832 58 791 680 7 99 320 224 761 127 50...

output:

15675138

result:

ok single line: '15675138'

Test #3:

score: 10
Accepted
time: 9ms
memory: 9720kb

input:

10000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822
...

output:

453173522

result:

ok single line: '453173522'

Test #4:

score: 10
Accepted
time: 55ms
memory: 28276kb

input:

100000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822...

output:

181864911

result:

ok single line: '181864911'

Test #5:

score: 10
Accepted
time: 22ms
memory: 14952kb

input:

1
100001
990117072 121266257 502101444 506187797 152265724 887855716 21575364 747489891 3913373 252828825 925488373 869945258 957255916 909604725 337241170 254650067 235485017 619901983 240912374 769328282 249600354 66310996 621433473 134246045 799368852 533841194 911465239 114696140 236494004 44433...

output:

672785783

result:

ok single line: '672785783'

Test #6:

score: 10
Accepted
time: 108ms
memory: 23816kb

input:

10
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
49733
22624218 300982665 75514183 17307023 151891674 818814124 681421086 983939896 975213637 388337097 728609775 503839345 909679593 275227646 722966525 313571842 143077312 3...

output:

5175380

result:

ok single line: '5175380'

Test #7:

score: 10
Accepted
time: 99ms
memory: 21184kb

input:

100
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822
14...

output:

691155161

result:

ok single line: '691155161'

Test #8:

score: 10
Accepted
time: 91ms
memory: 23220kb

input:

1000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822
1...

output:

265274205

result:

ok single line: '265274205'

Test #9:

score: 10
Accepted
time: 75ms
memory: 24724kb

input:

10000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822
...

output:

682655928

result:

ok single line: '682655928'

Test #10:

score: 10
Accepted
time: 124ms
memory: 37656kb

input:

100000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822...

output:

702441060

result:

ok single line: '702441060'