QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209652#7177. Many Many Cyclessumi007WA 1ms5668kbC++142.4kb2023-10-10 16:24:392023-10-10 16:24:39

Judging History

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

  • [2023-10-10 16:24:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5668kb
  • [2023-10-10 16:24:39]
  • 提交

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] = 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: 1ms
memory: 3628kb

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: 1ms
memory: 5668kb

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: -100
Wrong Answer
time: 1ms
memory: 3704kb

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:

wrong answer expected '2', found '-2'