QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#209654 | #7177. Many Many Cycles | sumi007 | WA | 1ms | 5872kb | C++14 | 2.4kb | 2023-10-10 16:25:11 | 2023-10-10 16:25:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define i64 __int128
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(i) i&(-i)
const int N = 5e3+5;
int n,m,vis[N],lim[N],on[N*2],dep[N],lca[N][N];
ll cost[N];
int fa[N][15];
struct G{
ll u,v,w;
}g[N*2];
vector<ll> e[N],path;
void dfs(int u,int eid){
for(int i=1;i<=12;i++) fa[u][i] = fa[fa[u][i-1]][i-1];
vis[u] = 1;
for(int id:e[u]){
if(id==eid) continue;
int v=g[id].v,w = g[id].w;
if(vis[v]) continue;
fa[v][0] = u,on[id] = 1,dep[v] = dep[u]+1;
cost[v] = cost[u]+w;
dfs(v,id);
}
}
ll dis(int u,int v){
return cost[u]+cost[v]-2*cost[lca[u][v]];
}
int ask(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int st=lim[u];
for(int i=st;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u = fa[u][i];
if(u==v) return u;
st = lim[v];
for(int i=st;i>=0;i--) if(fa[u][i]!=fa[v][i]) u = fa[u][i],v = fa[v][i];
return u;
}
bool cmp_dep(int x,int y){
return dep[x]>dep[y];
}
int main(){
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=m;i++){
cin >> g[i].u >> g[i].v >> g[i].w;
int u=g[i].u,v=g[i].v;
e[u].pb(i),e[v].pb(i);
}
for(int i=1;i<=n;i++) if(!vis[i]) dep[i] = 1,dfs(i,0);
for(int i=1;i<=n;i++) lim[i] = log2(n);
for(int i=1;i<=m;i++) if(!on[i]) path.pb(i);
for(int i=1;i<=n;i++){
lca[i][i] = i;
for(int j=i+1;j<=n;j++){
lca[j][i] = lca[i][j] = ask(i,j);
}
}
ll ans = 0,siz = path.size();
vector<int> p;
for(int i=0;i<siz;i++){
int a=g[path[i]].u,b=g[path[i]].v;
ll w0 = dis(a,b)+g[path[i]].w;
if(!ans) ans = w0;
else ans = __gcd(ans,w0);
// if(m>100) cout << w0 << '\n';
for(int j=i+1;j<siz;j++){
int c=g[path[j]].u,d=g[path[j]].v;
ll w1 = dis(c,d)+g[path[j]].w;
p.pb(lca[a][c]),p.pb(lca[b][c]);
p.pb(lca[a][d]),p.pb(lca[b][d]);
sort(p.begin(),p.end(),cmp_dep);
if(p[0]!=p[1]) ans = __gcd(ans,w0+w1-2*dis(p[0],p[1]));
// if(m>100 && p[0]!=p[1]) cout << "SP" << w0+w1-2*dis(p[0],p[1]) << '\n';
p.clear();
}
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4020kb
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: 3828kb
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: 0ms
memory: 4084kb
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: 1ms
memory: 4088kb
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: -100
Wrong Answer
time: 0ms
memory: 5872kb
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:
1
result:
wrong answer expected '3', found '1'