QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#348563#4895. Lovely DogsANIG0 150ms35296kbC++142.2kb2024-03-09 19:34:042024-03-09 19:34:05

Judging History

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

  • [2024-03-09 19:34:05]
  • 评测
  • 测评结果：0
  • 用时：150ms
  • 内存：35296kb
查看
  • [2024-03-09 19:34:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,k,siz[N],mk[N],w[N],f[N],mu[N],hs[N],g[N],jl[N],idx,res,pw[N],rs[N];
vector<int>p[N],ys[N];
bool cmp(int a,int b){
    return siz[a]<siz[b];
}
void clr(){
    while(idx)g[jl[idx]]=0,idx--;
}
void add(int x){
    //cout<<x<<endl;
    for(auto i:ys[x])g[i]+=f[x],jl[++idx]=i;
    for(auto i:ys[x]){
        int cd=__gcd(x,pw[i]),t=pw[i]/cd;
        if(cd<=n)res+=mu[i]*g[t]*f[x];
       // cout<<i<<" "<<t<<" "<<mu[i]<<" "<<g[t]<<endl;
    }
}
void dfs1(int x){
    mk[x]=1;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c])continue;
        dfs1(c);
        siz[x]+=siz[c];
    }
    sort(p[x].begin(),p[x].end(),cmp);
    siz[x]++;
    mk[x]=0;
}
void dfs3(int x){
    mk[x]=1;add(w[x]);
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c])continue;
        dfs3(c);
    }
    mk[x]=0;
}
void dfs2(int x){
    mk[x]=1;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c])continue;
        clr();res=0;
        dfs2(c);
    }
    for(int i=0;i<p[x].size()-1;i++){
        int c=p[x][i];
        if(mk[c])continue;
        dfs3(c);
    }
    add(w[x]);
    rs[x]=res;
    mk[x]=0;
}
int gets(int x){
    int res=1;
    for(int i=2;i*i<=x;i++){
        int cnt=0;
        while(x%i==0)x/=i,cnt++;
        if(cnt&1)res=-res;
    }
    if(x>1)res=-res;
    return res;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        p[x].push_back(y);
        p[y].push_back(x);
    }
    for(int i=1;i<=n;i++)cin>>w[i],f[i]=gets(i);
    for(int i=1;i<=n;i++)mu[i]=1;
    for(int i=2;i<=n;i++){
        if(!hs[i]){
            for(int j=i;j<=n;j+=i){
                if(j/i%i)mu[j]=-mu[j];
                else mu[j]=0;
                hs[j]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        pw[i]=1;
        for(int j=1;j<=k+1;j++){
            pw[i]=pw[i]*i;
            if(pw[i]>1e10)pw[i]=1e10+1;
        }
    }
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)ys[j].push_back(i);
    dfs1(1);
    dfs2(1);
    for(int i=1;i<=n;i++)cout<<rs[i]<<" ";
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 23764kb

input:

20 2
18 8
18 11
13 19
10 8
9 11
4 8
9 15
9 17
2 1
13 18
20 18
1 8
12 17
7 16
5 11
16 15
6 19
14 16
1 3
2 15 5 13 20 6 16 18 9 19 17 7 14 10 11 3 1 12 4 8

output:

14 1 1 1 0 1 0 10 2 1 4 1 6 1 0 0 2 5 1 0

result:

wrong answer 1st words differ - expected: '16', found: '14'

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 8ms
memory: 25392kb

input:

2000 1
134 1468
867 1750
351 1220
1690 1888
1685 134
585 282
1142 643
206 271
260 1833
1987 770
1029 1667
322 1371
341 518
601 915
119 893
1933 1502
951 1785
1056 1630
1957 1208
96 55
1508 1212
331 427
505 151
1378 1486
1545 697
1459 629
202 997
180 1917
1638 1177
1244 1896
302 658
1433 1605
1318 19...

output:

-160 -3 0 0 0 0 0 0 0 -3 0 0 0 1 0 -2 0 0 0 2 0 -13 0 0 0 0 0 0 175 -4 0 -1 -1 0 0 0 0 0 0 0 -18 0 0 0 0 -33 0 -1 0 -2 -22 0 -16 0 -1 4 0 0 1 0 0 0 5 0 0 0 -2 -10 0 0 17 0 0 0 -1 -2 0 1 0 0 0 -10 0 0 0 0 -2 0 0 0 0 0 -1 -1 -1 -1 0 35 0 0 60 -7 0 4 0 0 0 0 11 -4 15 0 0 7 0 -3 0 0 0 0 -11 0 0 0 0 0 -1...

result:

wrong answer 1st words differ - expected: '581', found: '-160'

Subtask #3:

score: 0
Runtime Error

Test #45:

score: 0
Runtime Error

input:

200000 20
117994 12616
53490 106425
103660 50033
132640 78252
58384 19939
69183 10015
39098 165030
179856 130356
65245 57831
18234 83378
4240 154896
177149 102260
4634 180087
132390 19627
98506 60775
1890 120740
87908 21917
41323 192721
181885 96684
69412 139951
9800 38301
59025 29879
186185 81402
1...

output:

result:

Subtask #4:

score: 0
Runtime Error

Test #50:

score: 0
Runtime Error

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

result:

Subtask #5:

score: 0
Runtime Error

Test #55:

score: 0
Runtime Error

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

result:

Subtask #6:

score: 0
Wrong Answer

Test #78:

score: 0
Wrong Answer
time: 150ms
memory: 35296kb

input:

50000 1
8097 41839
17674 41774
40520 8024
5786 38261
20664 43471
1217 49276
11185 40807
14186 25584
31704 14814
42333 41475
13053 39565
45938 30104
5826 39463
5031 10814
43784 6042
58 33849
42978 18978
36307 33276
34769 4351
27884 37532
27528 29431
29451 39345
10946 9667
19016 47269
7911 30103
10308...

output:

3456971935 0 0 0 0 0 0 -1 0 -4 0 0 4 0 0 0 0 0 0 0 0 -6 -1 -5 0 -4 0 2 -2 2 0 0 1 0 0 0 0 0 0 0 -1 -2 -1 0 -1 0 -3 0 2 0 0 2 -1 6 0 0 17 0 0 0 0 0 0 -27 0 -1 14 -2 32 -1 -8 19 0 0 3 0 -1 -2 1 1 6 -1 -1 0 -1 0 0 0 0 0 -1 0 0 -5 -6 -1 0 0 -5 0 0 0 2 0 0 -3 -43 0 0 0 0 0 0 0 4 0 1 0 0 0 0 0 0 0 0 0 0 0...

result:

wrong answer 1st words differ - expected: '-9152', found: '3456971935'

Subtask #7:

score: 0
Runtime Error

Test #103:

score: 0
Runtime Error

input:

200000 1
118863 188865
188022 168616
118976 119404
178852 33449
81624 40431
151228 160976
68943 136313
57200 117631
147789 139875
100240 55537
164811 145415
103548 186750
15010 168029
155731 107005
69836 1502
86171 122700
83448 131948
189162 94464
128210 2509
49724 183329
174782 192641
27687 71315
1...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-02 20:36:36 | OpenSource Project