QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#218260 | #7177. Many Many Cycles | CharlieVinnie | WA | 1ms | 3704kb | C++17 | 1.6kb | 2023-10-17 21:52:21 | 2023-10-17 21:52:22 |
Judging History
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'