QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#218260#7177. Many Many CyclesCharlieVinnieWA 1ms3704kbC++171.6kb2023-10-17 21:52:212023-10-17 21:52:22

Judging History

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

  • [2023-10-17 21:52:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3704kb
  • [2023-10-17 21:52:21]
  • 提交

answer

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
#define range basic_string_view
using namespace std; typedef long long ll; using ull = unsigned long long;
mt19937_64 rng(190345);
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    int n,m; cin>>n>>m; vector<vector<pair<int,int>>> to(n+1); For(i,1,m) { int x,y,z; cin>>x>>y>>z; to[x].emplace_back(y,z); to[y].emplace_back(x,z); }
    vector<ll> dis(n+1); vector<int> lis,val(n+1),fa(n+1),vis(n+1); int vcnt=0; vector<ull> hsh(n+1); ll ans=0; map<ull,ll> mp;
    function<void(int,int)> dfs=[&](int u,int pa){
        lis.push_back(u); vis[u]=++vcnt;
        for(auto [v,e]:to[u]){
            if(!vis[v]) val[v]=e,fa[v]=u,dis[v]=dis[u]+e,dfs(v,u),hsh[u]^=hsh[v];
            else if(v!=pa&&vis[v]<vis[u]) { ull x=rng(); mp[x]+=e; ans=__gcd(ans,dis[u]-dis[v]+e); hsh[v]^=x; hsh[u]^=x; }
        }
    };
    dfs(1,0); debug(hsh); debug(fa);
    For(i,2,n) mp[hsh[i]]+=val[i];
    for(auto [_,x]:mp) ans=__gcd(ans,x*2);
    debug(ans);
    cout<<ans<<'\n';
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: October 17 Tue, 21 : 16 : 12

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3532kb

input:

4 4
1 2 1
2 3 1
3 4 1
4 1 1

output:

4

result:

ok answer is '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

4 5
1 2 1
1 3 2
1 4 1
2 3 1
3 4 1

output:

4

result:

ok answer is '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

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

output:

2

result:

ok answer is '2'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

20 50
1 2 18468
1 3 26501
3 4 15725
3 5 29359
3 6 24465
6 7 28146
7 8 16828
2 9 492
8 10 11943
8 11 5437
8 12 14605
3 13 154
7 14 12383
6 15 18717
9 16 19896
8 17 21727
16 18 11539
16 19 19913
18 20 26300
11 3 2
17 1 1
16 2 2
15 1 1
10 3 2
9 1 2
19 2 1
6 1 2
7 3 1
17 3 2
15 3 2
8 6 2
5 1 2
8 1 2
12 ...

output:

1

result:

ok answer is '1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

100 150
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

3

result:

ok answer is '3'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

100 130
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

7

result:

ok answer is '7'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

100 200
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

4

result:

ok answer is '4'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

100 190
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

2

result:

ok answer is '2'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

3

result:

ok answer is '3'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

1

result:

ok answer is '1'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

1000 1600
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

1

result:

ok answer is '1'

Test #12:

score: -100
Wrong Answer
time: 1ms
memory: 3488kb

input:

100 190
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

2

result:

wrong answer expected '4', found '2'