oj.uz

Submission #771861

# Submission time Handle Problem Language Result Execution time Memory
771861 2023-07-03T10:37:02 Z gagik_2007 Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 25464 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
const ll LG=25;
ll n,m,k;
vector<int>g[N];
bool used[N];
bool cikli_papa[N];
int cikl[N];
int a[N];
vector<int>cikler;
set<pair<int,int>>koxer;
vector<int>gg[N];
int up[N][LG];
int dist[N][LG];
int tin[N],tout[N];
int timer=0;
bool arinq[N];

int ciklGti(int p, int v, int par){
    used[v]=true;
    for(int to:g[v]){
        if(!used[to]){
            int res=ciklGti(p, to, v);
            if(res!=-1){
                if(cikli_papa[v])cikl[p]=v;
                return res + 1;
            }
        }
        else if(to==p&&to!=par){
            if(cikli_papa[v])cikl[p]=v;
            return 1;
        }
    }
    return -1;
}

void dfs(int v, int par=-1){
    tin[v]=timer++;
    up[v][0]=(par==-1?v:par);
    dist[v][0]=(par==-1?0:a[par]);
    for(int to:gg[v]){
        if(to!=par){
            dfs(to,v);
        }
    }
    tout[v]=timer++;
}

bool is_papa(int v, int u){
    return (tin[v]<=tin[u]&&tout[v]>=tout[u]);
}

void lca_precalc() {
    for(int i=1;i<LG;i++){
        for(int v=1;v<=n;v++){
            up[v][i]=up[up[v][i-1]][i-1];
            dist[v][i]=dist[v][i-1]+dist[up[v][i-1]][i-1];
        }
    }
}

int lca(int v, int u){
    if(is_papa(v,u))return v;
    if(is_papa(u,v))return u;
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[v][i],u)){
            v=up[v][i];
        }
    }
    return up[v][0];
}

int find_dist(int v, int u){
    if(v==u)return a[v];
    int papa=lca(u,v);
    int ans=0;
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[v][i],papa)){
            ans+=dist[v][i];
            v=up[v][i];
        }
    }
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[u][i],papa)){
            ans+=dist[u][i];
            u=up[u][i];
        }
    }
    ans+=a[v];
    ans+=a[u];
    if(papa!=v&&papa!=u){
        ans+=a[papa];
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int v=1;v<=n;v++){
        fill(used,used+n+1,false);
        int res=ciklGti(v,v,v);
        if(res!=-1){
            if(cikl[v]==0){
                cikl[v]=v;
                cikli_papa[v]=true;
                cikler.push_back(v);
                a[v]=res;
            }
        }
        else{
            cikl[v]=v;
            cikler.push_back(v);
            a[v]=1;
        }
    }
    // cout<<endl;
    // for(int v:cikler)cout<<v<<" "<<a[v]<<endl;
    // cout<<endl;
    // for(int v=1;v<=n;v++){
    //     cout<<cikl[v]<<" ";
    // }
    // cout<<endl;
    for(int v=1;v<=n;v++){
        for(int to:g[v]){
            if(cikl[v]!=cikl[to])
            koxer.insert({cikl[v],cikl[to]});
            if(cikl[v]!=cikl[to])
            koxer.insert({cikl[to],cikl[v]});
        }
    }
    for(auto e:koxer){
        gg[e.ff].push_back(e.ss);
        gg[e.ss].push_back(e.ff);
    }
    for(int v:cikler){
        if(tout[v]==0){
            dfs(v);
        }
    }
    lca_precalc();
    ll ans=0;
    for(int v:cikler){
        for(int u:cikler){
            if(u!=v){
                int cur=find_dist(u,v);
                ans+=cur-a[u]-a[v];
                ans+=(cur-a[u]-1)*(a[v]-1);
                ans+=(cur-a[v]-1)*(a[u]-1);
                ans+=(cur-2)*(a[v]-1)*(a[u]-1);
            }
        }
    }
    for(int v:cikler){
        ans+=a[v]*(a[v]-1)*(a[v]-2);
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 25464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 14832 KB Output is correct
2 Correct 278 ms 14840 KB Output is correct
3 Correct 580 ms 14836 KB Output is correct
4 Execution timed out 1073 ms 14796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 17756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 14836 KB Output is correct
2 Correct 739 ms 14836 KB Output is correct
3 Execution timed out 1072 ms 14804 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 17764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -